C*O
发帖数: 389 | 1 3个已经排序的整数数列，找到common elements
简单想法， i,j,k 三个指针分别指向3个数组A[m],B[n],C[l]
若i,j,k所指数一样
则输出1个common element.++i,++j,++k
否则
判断i,j,k所指的数，哪一个是最小的 min_index
++min_index
循环，直到有1个数组遍历完
最坏情况 m+n+l 算法
请问能不能再继续优化，
明天on-site 很有可能问这个
哈哈 |
l*********8
发帖数: 4642 | 2 use your method to search common elements of the first two arrays. Once you
find one, binary search it in C[].
【在 C*O 的大作中提到】
: 3个已经排序的整数数列，找到common elements
: 简单想法， i,j,k 三个指针分别指向3个数组A[m],B[n],C[l]
: 若i,j,k所指数一样
: 则输出1个common element.++i,++j,++k
: 否则
: 判断i,j,k所指的数，哪一个是最小的 min_index
: ++min_index
: 循环，直到有1个数组遍历完
: 最坏情况 m+n+l 算法
: 请问能不能再继续优化，
|
l*********8
发帖数: 4642 | 3 Are there duplicated elements in these arrays? If yes, do you need to
output multiple elements that have same value?
【在 C*O 的大作中提到】
: 3个已经排序的整数数列，找到common elements
: 简单想法， i,j,k 三个指针分别指向3个数组A[m],B[n],C[l]
: 若i,j,k所指数一样
: 则输出1个common element.++i,++j,++k
: 否则
: 判断i,j,k所指的数，哪一个是最小的 min_index
: ++min_index
: 循环，直到有1个数组遍历完
: 最坏情况 m+n+l 算法
: 请问能不能再继续优化，
|
g**u
发帖数: 504 | 4 这样worst case复杂度就增加了吧
本来第三个数列只要遍历一遍的，现在可能要做很多次binary search.
假设三个数列都是n长度，本来worst case 是3n=O(n),现在worst case是2n+nlogn-=O(
nlogn).
you
【在 l*********8 的大作中提到】
: use your method to search common elements of the first two arrays. Once you
: find one, binary search it in C[].
|
C*O
发帖数: 389 | 5 这就不知道啦
别人贴的面经
【在 l*********8 的大作中提到】
: Are there duplicated elements in these arrays? If yes, do you need to
: output multiple elements that have same value?
|
C*O
发帖数: 389 | 6 对
http://www.leetcode.com/2010/03/here-is-phone-screening-questio
这是大牛的解，不过是2 sorted array
O(
【在 g**u 的大作中提到】
: 这样worst case复杂度就增加了吧
: 本来第三个数列只要遍历一遍的，现在可能要做很多次binary search.
: 假设三个数列都是n长度，本来worst case 是3n=O(n),现在worst case是2n+nlogn-=O(
: nlogn).
:
: you
|
p*****2
发帖数: 21240 | 7
最小的可以一直加到等于最大值。这样不用每次都比较。
【在 C*O 的大作中提到】
: 3个已经排序的整数数列，找到common elements
: 简单想法， i,j,k 三个指针分别指向3个数组A[m],B[n],C[l]
: 若i,j,k所指数一样
: 则输出1个common element.++i,++j,++k
: 否则
: 判断i,j,k所指的数，哪一个是最小的 min_index
: ++min_index
: 循环，直到有1个数组遍历完
: 最坏情况 m+n+l 算法
: 请问能不能再继续优化，
|
C*O
发帖数: 389 | 8 对，犀利
这算一个优化
【在 p*****2 的大作中提到】
:
: 最小的可以一直加到等于最大值。这样不用每次都比较。
|
l*****a
发帖数: 14598 | 9 如何知道小于最大值呢？
貌似还是要一个一个跟最大值比吧
【在 C*O 的大作中提到】
: 对，犀利
: 这算一个优化
|
C*O
发帖数: 389 | 10 那就返回，最大值，和最小值的index
【在 l*****a 的大作中提到】
: 如何知道小于最大值呢？
: 貌似还是要一个一个跟最大值比吧
|
|
|
p*****2
发帖数: 21240 | 11 主要是变成两两比
如何知道小于最大值呢？貌似还是要一个一个跟最大值比吧
★ Sent from iPhone App: iReader Mitbbs Lite 7.52
【在 l*****a 的大作中提到】
: 如何知道小于最大值呢？
: 貌似还是要一个一个跟最大值比吧
|
l*****a
发帖数: 14598 | 12 if so
why not use the same way to find the common of the first 2 arrays?
you
【在 l*********8 的大作中提到】
: use your method to search common elements of the first two arrays. Once you
: find one, binary search it in C[].
|
l*****a
发帖数: 14598 | 13 wrong.
你第一次binary search之后，旧已经大大缩小了下一次binary search的范围
so the time complexity should not be nlgn
O(
【在 g**u 的大作中提到】
: 这样worst case复杂度就增加了吧
: 本来第三个数列只要遍历一遍的，现在可能要做很多次binary search.
: 假设三个数列都是n长度，本来worst case 是3n=O(n),现在worst case是2n+nlogn-=O(
: nlogn).
:
: you
|
l*********8
发帖数: 4642 | 14 It we use binary search for two arrays, we need binary search on the
second array for each elements from the first array.
If there are NOT many common elements in the first two array, binary
search on the third array could be faster than iterating thought array 3.
But I agree that my method can perform worse in some cases.
【在 l*****a 的大作中提到】
: if so
: why not use the same way to find the common of the first 2 arrays?
:
: you
|
p*****2
发帖数: 21240 | 15 大牛又有时间过来指导了?
wrong.你第一次binary search之后，旧已经大大缩小了下一次binary search的范围so
the time complexity should not b........
★ Sent from iPhone App: iReader Mitbbs Lite 7.52
【在 l*****a 的大作中提到】
: wrong.
: 你第一次binary search之后，旧已经大大缩小了下一次binary search的范围
: so the time complexity should not be nlgn
:
: O(
|
c****p
发帖数: 6474 | 16 worst case
【在 l*****a 的大作中提到】
: wrong.
: 你第一次binary search之后，旧已经大大缩小了下一次binary search的范围
: so the time complexity should not be nlgn
:
: O(
|
l*****a
发帖数: 14598 | 17 worst case for binary search is O(n)
so maybe here the worst case will be O(n2)?
【在 c****p 的大作中提到】
: worst case
|
g**u
发帖数: 504 | 18 那如果第三列最小的数都比前两列最大的数大呢？
前两列每次找到一个common element， 第三列都要整个搜索一遍吧
当然在这种情况下，如前面贴说的，最小的那个可以一直增加到最大的那个。这样前两
列的common element 就会全部忽略掉，因为第三列的头一个数始终是最大的。
【在 l*****a 的大作中提到】
: wrong.
: 你第一次binary search之后，旧已经大大缩小了下一次binary search的范围
: so the time complexity should not be nlgn
:
: O(
|
l*********8
发帖数: 4642 | 19 worst case of binary search ( O(n) ) happens on extreme unbalanced binary
tree but not in this case. Here we do binary search on an array. It costs
at most log2(n) comparisons.
【在 l*****a 的大作中提到】
: worst case for binary search is O(n)
: so maybe here the worst case will be O(n2)?
|
C*O
发帖数: 389 | 20 你这个方法，还需要空间
不经济
【在 l*********8 的大作中提到】
: It we use binary search for two arrays, we need binary search on the
: second array for each elements from the first array.
: If there are NOT many common elements in the first two array, binary
: search on the third array could be faster than iterating thought array 3.
: But I agree that my method can perform worse in some cases.
|
|
|
l*********8
发帖数: 4642 | 21 I don't want to store all the common elements in the first two arrays. I
just wanted to say that my method could be better in some cases. For
example, it's better if the first two arrays are much much shorter than
the last array.
【在 C*O 的大作中提到】
: 你这个方法，还需要空间
: 不经济
|
C*O
发帖数: 389 | 22 en 我没看清
example,
【在 l*********8 的大作中提到】
: I don't want to store all the common elements in the first two arrays. I
: just wanted to say that my method could be better in some cases. For
: example, it's better if the first two arrays are much much shorter than
: the last array.
|
g**u
发帖数: 504 | 23 If there are two much shorter arrays, we can first find common elements for
those short ones and then binary search the long one.
If one array is much shorter than other two arrays, for each element in the
first array, we first binary search that element in the second shortest
array, if there exists, we then binary search it in the longest one.
It really depends.
【在 l*********8 的大作中提到】
: I don't want to store all the common elements in the first two arrays. I
: just wanted to say that my method could be better in some cases. For
: example, it's better if the first two arrays are much much shorter than
: the last array.
|
l*********8
发帖数: 4642 | 24 for two arrays, using binary search is O(n*logm), where n is the length of
the first array, m is the length of the second array. Directly scanning the
two arrays is O(n+m). If n << m, then n*logm < o+m. In this case, binary
search is better.
for
the
【在 g**u 的大作中提到】
: If there are two much shorter arrays, we can first find common elements for
: those short ones and then binary search the long one.
: If one array is much shorter than other two arrays, for each element in the
: first array, we first binary search that element in the second shortest
: array, if there exists, we then binary search it in the longest one.
: It really depends.
|
