## [LeetCode题解]从两个有序数组的并集中寻找第k小元素 作者是 在线疯狂 发布于 2015年2月5日 在 算法.

Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.

## 朴素解法的优化, O(k):

``````int findKthSMallest(int[] A, int[] B, int k) {
int a_offset = 0, b_offset = 0;
if (A.length + B.length < k) return -1;

while (true) {
if (a_offset < A.length) {
while (b_offset == B.length ||
A[a_offset] <= B[b_offset]) {
a_offset++;
if (a_offset + b_offset == k) return A[a_offset];
}
}
if (b_offset < B.length) {
while (a_offset == A.length ||
A[a_offset] >= B[b_offset]) {
b_offset++;
}
if (a_offset + b_offset == k) return B[b_offset];
}
}
}
``````

## 最佳解法, O(log m + log n):

```维护等式，
i + j = k – 1,

``````int findKthSmallest(int A[], int m, int B[], int n, int k) {
assert(m >= 0); assert(n >= 0); assert(k > 0); assert(k <= m+n);

int i = (int)((double)m / (m+n) * (k-1));
int j = (k-1) - i;

assert(i >= 0); assert(j >= 0); assert(i <= m); assert(j <= n);
// invariant: i + j = k-1
// Note: A[-1] = -INF and A[m] = +INF to maintain invariant
int Ai_1 = ((i == 0) ? INT_MIN : A[i-1]);
int Bj_1 = ((j == 0) ? INT_MIN : B[j-1]);
int Ai   = ((i == m) ? INT_MAX : A[i]);
int Bj   = ((j == n) ? INT_MAX : B[j]);

if (Bj_1 < Ai && Ai < Bj)
return Ai;
else if (Ai_1 < Bj && Bj < Ai)
return Bj;

assert((Ai > Bj && Ai_1 > Bj) ||
(Ai < Bj && Ai < Bj_1));

// if none of the cases above, then it is either:
if (Ai < Bj)
// exclude Ai and below portion
// exclude Bj and above portion
return findKthSmallest(A+i+1, m-i-1, B, j, k-i-1);
else /* Bj < Ai */
// exclude Ai and above portion
// exclude Bj and below portion
return findKthSmallest(A, i, B+j+1, n-j-1, k-j-1);
``````

Pingbacks已关闭。

1. boyxiaolong 发布于 2015年2月11日 20:16 #

第二种解法很简明 表示第三种 的确很难想