There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

中位数：有m个数，如果m为基数，那么中位数正好是第(m+1)/2个数；如果m为偶数，中位数应该是中间两个数（第m/2和第m/2+1个）的平均值

  • 第一种方法（默认数列从小到大排序）：
    1. 寻找中位数就是搜索处于有序数列中间的那个数，可以转化为搜索第k个数的值
    2. 如果数列A的长度大于等于k：首先比较数列A的第k个数x和数列B第一个数y。
      • 如果x小于等于y，那么x同时是所有数的第k个数，返回x；
      • 如果x大于y，很遗憾，x在top k以外，那么数列A的第k个到最后的数都被排除了，这样在新的数列A和数列B中搜索top k，这是一个递归过程。
    3. 如果数列A的长度小于k的话：那么就比较数列A的最后一个（第m个）x和数列B的第k-m个y。
      • 如果y大于等于x，那么就相当于A数列的m个数都在top k之内，而y正好是第k个。
      • 如果y小于x，那么y显然在top k内，但不是第k个。那么就可以把B数列中y以及y之前的k-m个数都去掉，然后查找第m个数（因为y以及y之前的数都在top k之内，去掉之后，要找的数由第k个变为第m个），递归搜索
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
class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
    	if ((m+n) % 2)
    		return findTopK(A, m, B, n, (m+n)/2+1);
    	else
    		return (findTopK(A, m, B, n, (m+n)/2) + findTopK(A, m, B, n, (m+n)/2+1))/2.0;
    }
    double findTopK(int A[], int m, int B[], int n, int k) {
    	if (m == 0)
    		return B[k-1];
    	if (n == 0)
    		return A[k-1];
    	if (k <= m) {
    		if (A[k-1] <= B[0])
    			return A[k-1];
    		else
    			return findTopK(B, n, A, k-1, k);
    	} else {
    		if (A[m-1] <= B[k-m-1])
    			return B[k-m-1];
    		else if ((A[m-1] > B[k-m-1])) {
    			return findTopK(A, m, B+k-m, m+n-k, m);
    		}
    	}
    }
};

  • 第二种方法：

    第一种方法中，最坏情况下的复杂度为O(k)。最坏情况就是top k的数字在数列A、B中各占一半。如果k特别大的话，会比较慢。

    第二中方法的思路就是每次从A、B数列中各选一部分，总共k个数；然后比较A、B选取部分的最后一个数。小的数肯定属于top k-1，大的数有可能是第k个，也有可能大于k。

    举例说明：假如选A的前u个，选B的前v个，u+v=k。然后比较A[u-1]和B[v-1]的大小。假如A[u-1]>B[v-1]，那么A[u-1]是这k个数最大的，B[0]到B[v-1]肯定属于前k-1个数。但A[u-1]也不一定是第k个，因为B中没选的数可能小于它。

    因为可以确定B[0]到B[v-1]这v个数都不可能是第k个，直接排除掉。然后采用递归的方式搜索剩下数字的第k-v个数（原来的第k个数）。

    在递归过程中，k的值在不断减小，如果等于1的话，直接返回A、B中的最小值。

    最后的问题：u和v的选择。尽量将k按比例分布在A、B上，也就是取A、B长度的一半。

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
class Solution {
public:
	double findMedianSortedArrays(int A[], int m, int B[], int n) {
		if ((m + n) % 2)
			return findTopK(A, m, B, n, (m + n) / 2 + 1);
		else
			return (findTopK(A, m, B, n, (m + n) / 2) + findTopK(A, m, B, n, (m + n) / 2 + 1)) / 2;
	}
	double findTopK(int A[], int m, int B[], int n, int k) {
		if (m == 0)
			return (double)B[k - 1];
		if (n == 0)
			return (double)A[k - 1];
		if (k == 1)
			return A[0] < B[0] ? A[0] : B[0];
		if (m > k)
			m = k;
		if (n > k)
			n = k;
		int mid_a, mid_b;
		if (m < n) {
			mid_a = (m-1)/2;
			mid_b = k - mid_a - 2;
		} else {
			mid_b = (n-1)/2;
			mid_a = k - mid_b - 2;
		}
		if (A[mid_a] < B[mid_b])
			return findTopK(A+mid_a+1, m-mid_a-1, B, n, k-mid_a-1);
		else if (A[mid_a] > B[mid_b]) 
			return findTopK(A, m, B+mid_b+1, n-mid_b-1, k-mid_b-1);
		else
			return A[mid_a];
	}
};