【在 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.
【在 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.
【在 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.
喔是这样。所以就是: 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讲的算法。
那我写一下吧 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讲的算法。
跟我用的差不多, 这种算法是 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