C*******n 发帖数: 24 | 1 Find the Kth smallest element in 2 sorted
array. so if you have 2 arrays
160;[1, 5, 9, 15, 20, 34] and [2, 6,
8, 10, 11, 19] and k = 5, the&
#160;answer is 8. Basically whats the
5th smallest number in the 2 arrays
combined.
Any ideas? | e******g 发帖数: 51 | 2
sorted
6,
the&
假设数组是A[n], B[m], n > m
if k > m + n return -1
else 对A[1:min(k,n)] 和 B[1:min(k,m)] 递归二分查找
【在 C*******n 的大作中提到】 : Find the Kth smallest element in 2 sorted : array. so if you have 2 arrays : 160;[1, 5, 9, 15, 20, 34] and [2, 6, : 8, 10, 11, 19] and k = 5, the& : #160;answer is 8. Basically whats the : 5th smallest number in the 2 arrays : combined. : Any ideas?
| n******f 发帖数: 318 | 3 O(Logn logm),最优解法,leetcode上有。
给A一个指针i,给B一个指针j。binary search,i,j初识化为k/2吧,如果,越界,适
当调整。比如其中一个取数组上限m,另一个取k-m。
如果A[i]
else if A[i]k, j= (j j-(i j-1))/2;
Else if A[i] >= B[j] and i j<=k, j=(j j-(j i-k-1))/2;
Else i = (i i-(i j-k-1)/2);
Repeat this process until i and j keep stable;
If (i j = k) return max(A[i], B[j]);
Else return min(A[i], B[j]);
Ipad打字真累,求轻拍。
一句话,就是找到两个数组的一个指针,使左边个数和等于k。 | n******f 发帖数: 318 | | n******f 发帖数: 318 | | k*********6 发帖数: 738 | 6 请问是leetcode上哪道题呀?
【在 n******f 的大作中提到】 : O(Logn logm),最优解法,leetcode上有。 : 给A一个指针i,给B一个指针j。binary search,i,j初识化为k/2吧,如果,越界,适 : 当调整。比如其中一个取数组上限m,另一个取k-m。 : 如果A[i]: else if A[i]k, j= (j j-(i j-1))/2; : Else if A[i] >= B[j] and i j<=k, j=(j j-(j i-k-1))/2; : Else i = (i i-(i j-k-1)/2); : Repeat this process until i and j keep stable; : If (i j = k) return max(A[i], B[j]); : Else return min(A[i], B[j]);
| w**7 发帖数: 22 | 7 find median of two sorted array | w*******s 发帖数: 138 | 8 应该是log(min(m,n,k))
【在 n******f 的大作中提到】 : o(logm logn)
| s**x 发帖数: 7506 | 9
Right, but a little more code that what leetcode site has.
The idea is do binary search in the array
A[0 .. Min(m,n,k)]
【在 w*******s 的大作中提到】 : 应该是log(min(m,n,k))
|
|