两个已排序数组A[m]、B[n]，求两者所有元素的第k大的元素
方法一
直接merge两个数组，然后求第K大的元素
方法二
使用计数器h记录当前已经找到第m大的元素；
使用两个指针pA和pB，分别指向数组A和B；
如果A当前元素小，pA++，m++;
如果B当前元素小，pB++，m++;
当m==k，得到答案。
O(k)时间，O(1)空间。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24private:
static int find_kth(std::vector<int>::const_iterator A, int m,
std::vector<int>::const_iterator B, int n,
int k) {
int i = 0;
int j = 0;
int h = 1;
if (0 == m) return B[k - 1];
if (0 == n) return A[k - 1];
if (1 == k) return min(A[0], B[0]);
while (i<m && j<n) {
if (A[i] <= B[j]) {
i++;
h++;
if (h == k) return A[i - 1];
} else {
j++;
h++;
if (h == k) return B[j - 1];
}
}
}
方法三
充分利用有序，每次排除k/2个元素，使用递归
·当A或B为空时，直接返回B[k-1]或A[k-1]
·当k==1时，返回min(A[0], B[0])
·当A[k/2 - 1] == B[k/2 - 1]时，返回A[k/2 - 1]或B[k/2 - 1]
假设A和B的元素个数都大于k/2，
·if (A[k/2 - 1] < B[k/2 - 1]) 排除A数组的k/2个元素。
·else if (A[k/2 - 1] > B[k/2 - 1]) 排除B数组的k/2个元素。
·else 找到了第k大的元素，直接返回A[k/2 - 1]或B[k/2 - 1]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48class Solution {
public:
double findMedianSortedArrays(const vector<int>& A, const vector<int>& B) {
const int m = A.size();
const int n = B.size();
int total = m + n;
if (total & 0x1) {
return find_kth(A.begin(), m,
B.begin(), n,
total/2 + 1);
} else {
return (
find_kth(A.begin(), m,
B.begin(), n,
total/2) +
find_kth(A.begin(), m,
B.begin(),n,
total/2 + 1)
) / 2.0;
}
}
private:
static int find_kth(std::vector<int>::const_iterator A, int m,
std::vector<int>::const_iterator B, int n,
int k) {
if (m > n) return find_kth(B, n,
A, m,
k);
if (m == 0) return *(B + k - 1);
if (k == 1) return min(*A, *B);
int ia = min(k/2, m);
int ib = k - ia;
if (*(A + ia - 1) < *(B + ib - 1)) {
return find_kth(A + ia, m - ia,
B, n,
k - ia);
} else if (*(A + ia - 1) > *(B + ib - 1)) {
return find_kth(A, m,
B + ib, n - ib,
k - ib);
} else {
return *(A + ia - 1);
}
}
};