h**o
发帖数: 548 | 1 以及Find Median Of Two Sorted Arrays。 复杂度是logM+logN还是logK?我觉得是
logM+logN，为什么有人说logK?
这道题一直不想看。但据说是高频。终于在2013末看懂了。 | r****c
发帖数: 2585 | 2 kth smallest is O(log(k))
medium is m+n/2 so it is O(log(m+n)). Notice O(log M + logN) is the same as
O(log (M+N)) so no difference. | h**o
发帖数: 548 | 3 为什么是logK?
http://leetcode.com/2011/01/find-k-th-smallest-element-in-union + logN. 因为对M和N分割。
as
【在 r****c 的大作中提到】
: kth smallest is O(log(k))
: medium is m+n/2 so it is O(log(m+n)). Notice O(log M + logN) is the same as
: O(log (M+N)) so no difference.
| b*******r
发帖数: 361 | 4 不懂
as
【在 r****c 的大作中提到】
: kth smallest is O(log(k))
: medium is m+n/2 so it is O(log(m+n)). Notice O(log M + logN) is the same as
: O(log (M+N)) so no difference.
| A*********c
发帖数: 430 | 5 这样考虑，既然是top K, 无论数组多长，两个数组K后面的全部可以一刀切掉，所以看
算法本身有没有这步功能，没有这步也可以加上，所以算法复杂度和M，N无关。
就像两个班级求前5名，必然在两个班级的前5名里出现，跟两个班级分别多大没关系。
在加上二分查找，所以是top K。
【在 h**o 的大作中提到】
: 为什么是logK?
: http://leetcode.com/2011/01/find-k-th-smallest-element-in-union + logN. 因为对M和N分割。
:
: as
| W*********y
发帖数: 481 | 6 O(log(M*N)) 和 O(log(M+N)) 不一样吧？
as
【在 r****c 的大作中提到】
: kth smallest is O(log(k))
: medium is m+n/2 so it is O(log(m+n)). Notice O(log M + logN) is the same as
: O(log (M+N)) so no difference.
| A*********c
发帖数: 430 | 7 O(log(M*N)) = O (log(M) + log(N))
log(M) <= log(M+N)
log(N) <= log(M+N)
O(log(M+N)) <= O(2*log(M+N)) = O(log(M+N));
right?
【在 W*********y 的大作中提到】
: O(log(M*N)) 和 O(log(M+N)) 不一样吧？
:
: as
| h**o
发帖数: 548 | 8 喔是这样。所以就是：
int findKthSmallest(int A[], int m, int B[], int n, int k) {
if ((m == 0 && n==0) || k >m+n) return INT_MIN;
int min_m = min(m, k);
int min_n = min(n, k);
return findKthSmallest_recur(A, min_m, B, min_n, k);
}
findKthSmallest_recur()就沿用leetcode讲的算法。
【在 A*********c 的大作中提到】
: 这样考虑，既然是top K, 无论数组多长，两个数组K后面的全部可以一刀切掉，所以看
: 算法本身有没有这步功能，没有这步也可以加上，所以算法复杂度和M，N无关。
: 就像两个班级求前5名，必然在两个班级的前5名里出现，跟两个班级分别多大没关系。
: 在加上二分查找，所以是top K。
| s********x
发帖数: 914 | 9 那我写一下吧
public static int findKthSmallestElementInTwoSortedArrays(int[] a, int i
, int m, int[] b, int j,
int n, int k) {
validate(a, b)；
if ( m > n) {
return findKthSmallestElementInTwoSortedArrays(b, j, n, a, i, m
,k);
} // now m <= n
// Boundary check
if (k > m + n) {
throw new IllegalArgumentException("k is too big");
} else if (k <= m) {
// cut two arrays to be both of size k because it can only
appear in top k of two arrays
m = k;
n = k;
} else if (n > k) {
// m < k
n = k;
} // other scenario is m < k and n < k
// i is the beginning index of a, m is the length of a
// j is the beginning index of b, n is the length of b
// invariant: i + j = k-1
// a has m elements now, and k <= (m+n) => m/(m+n)* (k-1) < m
// Note a[-1] = -INF and a[m] = +INF to maintain invariant
int ii = (int) ((double) m / (m + n) * (k - 1));
int jj = (k - 1) - ii;
int ai_1 = ii == 0 ? Integer.MIN_VALUE : a[i + ii - 1];
int bj_1 = jj == 0 ? Integer.MIN_VALUE : b[j + jj - 1];
int ai = ii == m ? Integer.MAX_VALUE : a[i + ii];
int bj = jj == n ? Integer.MAX_VALUE : b[j + jj];
if (bj_1 < ai && ai < bj)
return ai;
if (ai_1 < bj && bj < ai)
return bj;
// if none of the cases above, then it is either:
if (ai < bj)
// exclude Ai and below portion, we keep a[i+ii+1] and above
// exclude Bj and above portion
return findKthSmallestElementInTwoSortedArrays(a, i + ii + 1, m
- ii - 1, b, j, jj, k - ii
- 1);
else
/* Bj < Ai */
// exclude Ai and above portion
// exclude Bj and below portion
return findKthSmallestElementInTwoSortedArrays(a, i, ii, b, j +
jj + 1, n - jj - 1, k - jj
- 1);
}
【在 h**o 的大作中提到】
: 喔是这样。所以就是：
: int findKthSmallest(int A[], int m, int B[], int n, int k) {
: if ((m == 0 && n==0) || k >m+n) return INT_MIN;
: int min_m = min(m, k);
: int min_n = min(n, k);
: return findKthSmallest_recur(A, min_m, B, min_n, k);
: }
: findKthSmallest_recur()就沿用leetcode讲的算法。
| s**x
发帖数: 7506 | 10 跟我用的差不多， 这种算法是 log(min(k, m, n)).
code 简答些的貌似 logm+logn.
i
m
【在 s********x 的大作中提到】
: 那我写一下吧
: public static int findKthSmallestElementInTwoSortedArrays(int[] a, int i
: , int m, int[] b, int j,
: int n, int k) {
: validate(a, b)；
:
: if ( m > n) {
: return findKthSmallestElementInTwoSortedArrays(b, j, n, a, i, m
: ,k);
: } // now m <= n
| m********7
发帖数: 1368 | | s**x
发帖数: 7506 | 12 should be around 5 lines. log(min(n, m, k)) needs about 20.
【在 m********7 的大作中提到】
: O(lgm + lgn),15行代码搞定。。
| h******6
发帖数: 2697 | 13
求代码。。。
【在 m********7 的大作中提到】
: O(lgm + lgn),15行代码搞定。。
|
|
