f*********i
发帖数: 197 | 1 求递增二纬数组，就是排列按行递增，按列也递增的数组（m*n）的第k大的数。
请问有没有比较好的解法。 | c****9
发帖数: 164 | 2 大小为K的min heap去扫整个数组，O（MN）*logk，第一时间只有这个想法 | w****x
发帖数: 2483 | | w****x
发帖数: 2483 | 4 有种解法是基于数值的2分, 实现起来也很绕. 原题是给两个排序的数组 A, B. 如果a
->A, b->B, 求第k大的a + b, 可以化成杨氏矩阵求解, 没记错因该是Google的题, 我
见过最难的题之一 | D********g
发帖数: 650 | 5 maintain 一个size为m的min heap (这里假定m < n), heap里每个元素初始化为每行第
一个数字以及每个数字对应的行号。
然后取heap root所在行的下一个数字，replace root，heapify. 如果root所在行run
out，change root value to some MAX value, then heapify.
如此重复K-1次。root就是第K大的数。比较tricky的case是当root所在row run out.需
要找到下一个最小的数，check 其所在row的下一个数，如果也run out，则继续找下去
，直到找到为止。
这么看来用balanced search tree应该更合适，klog(m)的复杂度。
【在 f*********i 的大作中提到】
: 求递增二纬数组，就是排列按行递增，按列也递增的数组（m*n）的第k大的数。
: 请问有没有比较好的解法。
| l******c
发帖数: 2555 | 6 binary search from (0,0), to (m, n)
log(m + n)
amazon asked me this question during the phone interview
【在 f*********i 的大作中提到】
: 求递增二纬数组，就是排列按行递增，按列也递增的数组（m*n）的第k大的数。
: 请问有没有比较好的解法。
| g**x
发帖数: 373 | 7 Is it to find the K-th number, or to find "K"?
【在 l******c 的大作中提到】
: binary search from (0,0), to (m, n)
: log(m + n)
: amazon asked me this question during the phone interview
| l*********8
发帖数: 4642 | 8 find the K-th number
【在 g**x 的大作中提到】
: Is it to find the K-th number, or to find "K"?
| g**x
发帖数: 373 | 9 I am confused by what "lclclclc" said.
It is Ok to use binary search to find "k".
It seems not right to use binary search to get K-th number.
【在 l*********8 的大作中提到】
: find the K-th number
| g**x
发帖数: 373 | 10 K-way merge is good. But it doesn't gain the benefits of the condition that
each column is also in increasing order.
How about this:
Just build a size 3 min heap, using A[0,0], A[0,1], A[1,0].
1)Delete the root of the heap;
2)Add new root's two neighbors (suppose coordinates of new root is [i,j],
pick up [i+1,j] and [i,j+1]).
3)Loop 1),2) K-1 times; We got K-th elements at the root of the heap.
The time complexity is K Log(K) (For each loop, heap size increase at most,
so the heap size is K). It would be faster when K<
run
【在 D********g 的大作中提到】
: maintain 一个size为m的min heap (这里假定m < n), heap里每个元素初始化为每行第
: 一个数字以及每个数字对应的行号。
: 然后取heap root所在行的下一个数字，replace root，heapify. 如果root所在行run
: out，change root value to some MAX value, then heapify.
: 如此重复K-1次。root就是第K大的数。比较tricky的case是当root所在row run out.需
: 要找到下一个最小的数，check 其所在row的下一个数，如果也run out，则继续找下去
: ，直到找到为止。
: 这么看来用balanced search tree应该更合适，klog(m)的复杂度。
| | | s***5
发帖数: 2136 | 11 This is not right. Adding the two neighbors of the old root is not enough.
For example, to find the 4th smallest element, you need to add 3 new
elements (0,3), (2,2), (3,0) to the heap.
On average, at the k <= K step, you need to add sqrt(k) new elements to the
heap, not just two. The time complexity will be K*sqrt(K)*log(K), and the
space is O(K*sqrt(K)).
that
,
【在 g**x 的大作中提到】
: K-way merge is good. But it doesn't gain the benefits of the condition that
: each column is also in increasing order.
: How about this:
: Just build a size 3 min heap, using A[0,0], A[0,1], A[1,0].
: 1)Delete the root of the heap;
: 2)Add new root's two neighbors (suppose coordinates of new root is [i,j],
: pick up [i+1,j] and [i,j+1]).
: 3)Loop 1),2) K-1 times; We got K-th elements at the root of the heap.
: The time complexity is K Log(K) (For each loop, heap size increase at most,
: so the heap size is K). It would be faster when K<
| g**x
发帖数: 373 | 12 Could you give an example?
The two neighbors of the NEW root are enough to ensure the next minimum. The
rest are larger than either the two neighbors or the existing elements in
heap.
the
【在 s***5 的大作中提到】
: This is not right. Adding the two neighbors of the old root is not enough.
: For example, to find the 4th smallest element, you need to add 3 new
: elements (0,3), (2,2), (3,0) to the heap.
: On average, at the k <= K step, you need to add sqrt(k) new elements to the
: heap, not just two. The time complexity will be K*sqrt(K)*log(K), and the
: space is O(K*sqrt(K)).
:
: that
: ,
| s***5
发帖数: 2136 | 13 I double checked, and I was wrong. The only thing is that you need to check
if one of the two neighbors of the new root is already in the heap,
otherwise you add duplicated elements.
3*3 matrix
1 3 6
2 4 7
5 8 9
at k =3 when 3 is the root, you remove it and add its neighbors (4,6) to the
heap, but 4 is already in the heap since it is also the neighbor of 2.
The
【在 g**x 的大作中提到】
: Could you give an example?
: The two neighbors of the NEW root are enough to ensure the next minimum. The
: rest are larger than either the two neighbors or the existing elements in
: heap.
:
: the
| g**x
发帖数: 373 | 14 Right. Cannot have duplicated elements.
check
the
【在 s***5 的大作中提到】
: I double checked, and I was wrong. The only thing is that you need to check
: if one of the two neighbors of the new root is already in the heap,
: otherwise you add duplicated elements.
: 3*3 matrix
: 1 3 6
: 2 4 7
: 5 8 9
: at k =3 when 3 is the root, you remove it and add its neighbors (4,6) to the
: heap, but 4 is already in the heap since it is also the neighbor of 2.
:
| b***d
发帖数: 87 | 15 这个解法应该可行。
run
【在 D********g 的大作中提到】
: maintain 一个size为m的min heap (这里假定m < n), heap里每个元素初始化为每行第
: 一个数字以及每个数字对应的行号。
: 然后取heap root所在行的下一个数字，replace root，heapify. 如果root所在行run
: out，change root value to some MAX value, then heapify.
: 如此重复K-1次。root就是第K大的数。比较tricky的case是当root所在row run out.需
: 要找到下一个最小的数，check 其所在row的下一个数，如果也run out，则继续找下去
: ，直到找到为止。
: 这么看来用balanced search tree应该更合适，klog(m)的复杂度。
| l*********8
发帖数: 4642 | 16 what if K = m*n/2?
then Klog(K) becomes m*n*log(m*n)
that
,
【在 g**x 的大作中提到】
: K-way merge is good. But it doesn't gain the benefits of the condition that
: each column is also in increasing order.
: How about this:
: Just build a size 3 min heap, using A[0,0], A[0,1], A[1,0].
: 1)Delete the root of the heap;
: 2)Add new root's two neighbors (suppose coordinates of new root is [i,j],
: pick up [i+1,j] and [i,j+1]).
: 3)Loop 1),2) K-1 times; We got K-th elements at the root of the heap.
: The time complexity is K Log(K) (For each loop, heap size increase at most,
: so the heap size is K). It would be faster when K<
|
|
