首页 > ACM题库 > LeetCode > LeetCode-Median of Two Sorted Arrays
2014
07-15

LeetCode-Median of Two Sorted Arrays

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)).

题目:https://oj.leetcode.com/problems/median-of-two-sorted-arrays/

求将两个长度分别为m,n的已排序数组合并后的中位数。要求的时间复杂度为  O(log (m+n)),很显然需要用分治法。

这一篇文章介绍了当长度都为n时的分治算法求两个有序数组的中位数,做些修改后就可以用来解此题。

还有另外一种方法,用二分查找求解,当然都是分治的思想,只是途径有所不同。

这个二分查找是同时在两个数组中查找 排名为K的元素。我们的目标就是要在排名为 K=(m+n)/2+1的那个(假设m+n奇数)。

已数组A的 arr[m/2] 为key,在输入B中进行查找。找到 <= key 最大的那个元素的位置 r 。则可以确定key在两个数组中排名为:m/2 + r + 2.

例如:

int A[] = {1,3,5,7,8};
int B[] = {4,7,8,10};

key = arr[m/2] = arr[2] = 5, 在数组B中查找key可得 r=0, 因为4是 小于等于key的最大元素。 key的最终排名即为 2+0+2 = 4.

而我们要找的目标是排名为  (m+n)/2+1=5 的那个元素。因此在子数组 {7,8} 和 {7,8,10} 选择排名为1 (5-4=1)的元素即可。

如此递归下去,子数组的范围会不断缩小,复杂度为O(log (m+n))。

#include <iostream>
using namespace std;

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        if ((m+n) % 2 == 1)
            return findkthElement(A, m, B, n, (m+n)/2+1);
        else
            return ( findkthElement(A, m, B, n, (m+n)/2) +
            		findkthElement(A, m, B, n, (m+n)/2+1)
            		) / 2.0;
    }

    int findkthElement(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 == 1) return min(A[0], B[0]);
        if (m < n) return findkthElement(B, n, A, m, k);
        int i = m/2;
        int low = 0, high = n-1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (B[mid] <= A[i]) low = mid + 1; else high = mid - 1;
        }
        int j = high; //B[j] 是 <= A[i] 的那个最大的数

        if (i+j+2 == k) //i+j+2 是 A[i] 在两个数组的 排名
            return A[i];
        else if (i+j+2 < k)
            return findkthElement(A+i+1, m-i-1, B+j+1, n-j-1, k-i-j-2);
        else
            return findkthElement(A, i, B, j+1, k);
    }
};

int main(){
	Solution s;
	int A[] = {1,3,5,7,8};
	int B[] = {4,7,8,10};
	int m = sizeof(A)/ sizeof(A[0]);
	int n = sizeof(B)/sizeof(B[0]);
	int ran = s.findkthElement(A, m, B,n, 6);
	cout << ran << endl;
	return 0;
}

参考:https://oj.leetcode.com/discuss/2910/how-to-get-o-log-m-n-complexity-i-only-solved-it-in-o-m-n


  1. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  2. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。