俩数组求中位数

设数组A的长度为m, 数组B的长度为n， 两个数组都都是递增有序的。

求这两个数组的中位数

首先我们看看中位数的特点，一个大小为n的数组，

如果n是奇数，则中位数只有一个，数组中恰好有  (n-1)/2 个元素比中位数小。

如果n是偶数，则中位数有两个（下中位数和上中位数），这里我们只求下中位数，对于下中位数，

数组中恰好有(n-1)/2个元素比下中位数小。

此题中，中位数只有一个，它前面有 c = (m+n-1)/2 个数比它小。中位数要么出现在数组A中，

要么出现在数组B中，我们先从数组A开始找。考察数组A中的一个元素A[p]， 在数组A中，

有 p 个数比A[p]小，如果数组B中恰好有 c-p 个数比 A[p] 小， 则俩数组合并后就恰好有 c 个数比A[p]小，

于是A[p]就是要找的中位数。 如下图所示：

如果A[p] 恰好位于 B[c-p-1] 和 B[c-p] 之间，则 A[p] 是中位数

如果A[p] 小于 B[c-p-1] ，说明A[p] 太小了，接下来从 A[p+1] ~A[m-1]开始找

如果A[p] 大于 B[c-p] ，说明A[p] 太大了，接下来从 A[0] ~A[p-1]开始找。

如果数组A没找到，就从数组B找。

注意到数组A和数组B都是有序的，所以可以用二分查找。代码如下：

[cpp]  view plain copy

1. #include <stdio.h>  
2. #include <stdlib.h>  
3.   
4.   
5. /* 从数组A和B中找下中位数 */  
6. int find_median(int *A, int *B, int m, int n, int s, int t)  
7. {  
8.     int  p, c;  
9.   
10.     c = (m+n-1)/2;  /* 有多少个数小于下中位数 */  
11.     p = (s+t)/2;  
12.   
13.     /* 如果下中位数不在A中，就从数组B找 */  
14.     if (s > t) {  
15.         return find_median(B, A, n, m, 0, n-1);  
16.     }  
17.   
18.     /* 数组A中有p个数小于A[p], 当且进当数组B中有c-p个数小于A[p], A[p]才是中位数 */  
19.     if (A[p] >= B[c-p-1] && A[p] <= B[c-p]) {  
20.         return A[p];  
21.     }  
22.   
23.     /* A[p]太小了，从数组A中找一个更大的数尝试 */  
24.     if (A[p] < B[c-p-1]) {  
25.         return find_median(A, B, m, n, p+1, t);  
26.     }  
27.   
28.     /* A[p]太大了，从数组A中找一个更小的数尝试 */  
29.     return find_median(A, B, m, n, s, p-1);  
30. }  
31.   
32. int main()  
33. {  
34.     int m, n;  
35.     int A[]={1,3,5,7,8,9,10,12,24,45,65};  
36.     int B[]={2,4,6,10,11,12,13,14,17,19,20,34,44,45,66,99};  
37.   
38.     m = sizeof(A)/sizeof(int);  
39.     n = sizeof(B)/sizeof(int);  
40.   
41.     printf("%d\n", find_median(A, B, m, n, 0, m-1));  
42.   
43.     return 0;  
44. }  

Question

There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n))。

有两个排序的数组，长度都为n，求合并后的排序数组的中位数。

题目是《算法导论》上的一道习题，不过已多次出现在面试题当中。注意，此题中两个数组的长度是相等的。当然，长度不等的话也可以做，只是要多些判断条件。参考leetcode题目 Median of Two Sorted Arrays

方法1 直接遍历

直接的解法是遍历两个数组并计数，类似归并排序里面的有序数组的合并，复杂度为O（n）。代码如下：

01 #include <iostream>
02 #include <stdio.h>
03 using namespace std;
04
05 double getMedian(int arr1[],int arr2[], int n){
06     int i=0,j=0; //分别是 arr1， arr2的当前下标
07     int m1=-1,m2=-1; //保存两个中位数. 由于是2n个，肯定有两个中位数
08     for(int cnt=0; cnt<=n; cnt++){
09         if( i<n && (arr1[i] < arr2[j] || j >= n )){
10             m1 = m2;
11             m2 = arr1[i++];
12         }else{
13             m1 = m2;
14             m2 = arr2[j++];
15         }
16     }
17     return (m1+m2)/2.0;
18 }
19 int main()
20 {
21     int ar1[] = {1, 12, 15, 26, 38};
22     int ar2[] = {2, 13, 17, 30, 45};
23
24     int n1 = sizeof(ar1)/sizeof(ar1[0]);
25     int n2 = sizeof(ar2)/sizeof(ar2[0]);
26     if (n1 == n2)
27         printf("Median is %lf", getMedian(ar1, ar2, n1));
28     else
29         printf("Doesn't work for arrays of unequal size");
30     return 0;
31 }

方法2 分治法

要求的复杂度为O(log (m+n))，很显然需要用分治法求解。

假设数组A的中位数为m1，数组B为m2，例如：

ar1[] = {1, 12, 15, 26, 38}
ar2[] = {2, 13, 17, 30, 45}

m1 = 15 ，m2 = 17 。由于m1<m2，则可以确定中位数即为下面两个子数组的中位数 ：

[15, 26, 38]  和 [2, 13, 17]

重复这个步骤，可以得到   m1 = 26 m2 = 13. 得到两个子数组：

[15, 26] 和[13, 17]

这时，由于n=2，无法在继续分下去了。可以直接计算得：

1 median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
2                       = (max(15, 13) + min(26, 17))/2
3                       = (15 + 17)/2
4                       = 16

代码如下：

01 int median(int arr[], int n)
02 {
03     if (n%2 == 0)
04         return (arr[n/2] + arr[n/2-1])/2;
05     else
06         return arr[n/2];
07 }
08
09 int getMedian(int ar1[], int ar2[], int n) {
10     int m1;
11     int m2;
12     if (n <= 0)
13         return -1;
14     if (n == 1)
15         return (ar1[0] + ar2[0]) / 2;
16
17     if (n == 2)
18         return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2;
19
20     m1 = median(ar1, n);
21     m2 = median(ar2, n);
22     /* 相等可直接返回 */
23     if (m1 == m2)
24         return m1;
25     if (m1 < m2) {
26         if (n % 2 == 0)
27             return getMedian(ar1 + n/2-1, ar2, n/2 + 1);
28         else
29             return getMedian(ar1 + n/2, ar2, n/2+1);
30     } else {
31         if (n % 2 == 0)
32             return getMedian(ar2 + n/2-1, ar1, n/2+1);
33         else
34             return getMedian(ar2 + n/2, ar1, n/2+1);
35     }
36 }
37
38 int main()
39 {
40     int ar1[] = {1, 12, 10, 26, 38};
41     int ar2[] = {2, 13, 17, 30, 45};
42
43     int n1 = sizeof(ar1)/sizeof(ar1[0]);
44     int n2 = sizeof(ar2)/sizeof(ar2[0]);
45     if (n1 == n2)
46         printf("Median is %d", getMedian(ar1, ar2, n1));
47     else
48         printf("Doesn't work for arrays of unequal size");
49     return 0;
50 }

 

时间复杂度为 O(logn)。

这是一道非常经典的题。这题更通用的形式是，给定两个已经排序好的数组，找到两者所有元
素中第k 大的元素。
O(m + n) 的解法比较直观，直接merge 两个数组，然后求第k 大的元素。
不过我们仅仅需要第k 大的元素，是不需要“排序”这么复杂的操作的。可以用一个计数器，
记录当前已经找到第m 大的元素了。同时我们使用两个指针pA 和pB，分别指向A 和B 数组的第
一个元素，使用类似于merge sort 的原理，如果数组A 当前元素小，那么pA++，同时m++；如果
数组B 当前元素小，那么pB++，同时m++。最终当m 等于k 的时候，就得到了我们的答案，O(k)
时间，O(1) 空间。但是，当k 很接近m + n 的时候，这个方法还是O(m + n) 的。
有没有更好的方案呢？我们可以考虑从k 入手。如果我们每次都能够删除一个一定在第k 大元
素之前的元素，那么我们需要进行k 次。但是如果每次我们都删除一半呢？由于A 和B 都是有序
的，我们应该充分利用这里面的信息，类似于二分查找，也是充分利用了“有序”。
假设A 和B 的元素个数都大于k/2，我们将A 的第k/2 个元素（即A[k/2-1]）和B 的第k/2
个元素（即B[k/2-1]）进行比较，有以下三种情况（为了简化这里先假设k 为偶数，所得到的结
论对于k 是奇数也是成立的）：
• A[k/2-1] == B[k/2-1]
• A[k/2-1] > B[k/2-1]
• A[k/2-1] < B[k/2-1]
如果A[k/2-1] < B[k/2-1]，意味着A[0] 到A[k/2-1 的肯定在A [ B 的top k 元素的范围
内，换句话说，A[k/2-1 不可能大于A [ B 的第k 大元素。留给读者证明。
因此，我们可以放心的删除A 数组的这k/2 个元素。同理，当A[k/2-1] > B[k/2-1] 时，可
以删除B 数组的k/2 个元素。
当A[k/2-1] == B[k/2-1] 时，说明找到了第k 大的元素，直接返回A[k/2-1] 或B[k/2-1]
即可。
因此，我们可以写一个递归函数。那么函数什么时候应该终止呢？
• 当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]
代码
// LeetCode, Median of Two Sorted Arrays
// 时间复杂度O(log(m+n))，空间复杂度O(log(m+n))
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int total = m + n;
if (total & 0x1)
return find_kth(A, m, B, n, total / 2 + 1);
8 第2 章线性表
else
return (find_kth(A, m, B, n, total / 2)
+ find_kth(A, m, B, n, total / 2 + 1)) / 2.0;
}
private:
static int find_kth(int A[], int m, int B[], int n, int k) {
//always assume that m is equal or smaller than n
if (m > n) return find_kth(B, n, A, m, k);
if (m == 0) return B[k - 1];
if (k == 1) return min(A[0], B[0]);
//divide k into two parts
int ia = min(k / 2, m), 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];
}
};