这个题和leetcode的基本一样。用了更好点的思路。在A中折半猜是不是中位数，A中没有后在B中猜。最后猜到B[j]<=A[i]<=B[j+1]，此时，无论奇偶（2k+1或者2k个），A[i]都是第k+1那个。那么奇数时，A[i]是正中的那个；偶数时，A[i]是中位数两个里大的那个，小的那个要从B[j]和A[i-1]里选一个。
要注意的是A和B可能为空。而且要注意偶数的情况是，最后算出来的两个，要先判断位置j和i-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
|
#include <climits>int
median(vector<int> &A) {
int
n = A.size();
if
(n % 2 == 1) {
return
A[n/2];
} else
{
return
(A[n/2-1] + A[n/2]) / 2;
}
}int
median(vector<int> &A, vector<int> &B, int
l, int
r) {
if
(l > r) return
median(B, A, 0, B.size()-1);
int
an = A.size();
int
bn = B.size();
int
i = (l + r) / 2;
int
j = (an + bn) / 2 - i - 1;
if
(j >= 0 && A[i] < B[j]) {
return
median(A, B, i+1, r);
} else
if
(j < bn - 1 && A[i] > B[j+1]) {
return
median(A, B, l, i-1);
} else
{
if
((an + bn) % 2 == 1) {
return
A[i];
} else
{
int
another = INT_MIN;
if
(j >= 0 && j < B.size()) {
another = max(another, B[j]);
}
if
(i-1 > 0 && i-1 < A.size()) {
another = max(A[i-1], another);
}
return
(A[i] + another) / 2;
}
}
}int
median(vector<int> &arr1, vector<int> &arr2) {
if
(arr1.size() == 0) return
median(arr2);
if
(arr2.size() == 0) return
median(arr1);
return
median(arr1, arr2, 0, arr1.size()-1);
} |