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))
|
|
