LEETCODE算法:4. Median of Two Sorted Arrays

发表于 更新于 分类于 Waline： 阅读次数：

题目

There are two sorted arrays nums1 and nums2 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)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3] nums2 = [2]

The median is 2.0 Example 2:

nums1 = [1, 2] nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

题解

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
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size()>nums2.size())
        {//保证数组2的数组个数更多是为了保证j>=0
            return findMedianSortedArrays(nums2,nums1);
        }
        int imin=0,imax=nums1.size();
        while(imin<=imax)
        {//二分法
            int i=(imin+imax)/2;
            int j=(nums1.size()+nums2.size()+1)/2-i;
            if(i>imin&&nums1[i-1]>nums2[j])
            {//数组1的左侧最大值大于数组而右侧最小值，数组1的分割线要左移，i最大值减小
                imax=i-1;
            }else if(i<imax&&nums2[j-1]>nums1[i]){
                //数组2的左侧最大值大于数组1的右侧最小值，数组1的分割线右移，i的最小值增加
                imin=i+1;
            }else{
                //考虑i==0,j==0,i==nums1.size(),j==nums2.size()这些特例
                int maxleft=0;
                if(i==0) maxleft=nums2[j-1];
                else if(j==0) maxleft=nums1[i-1];
                else maxleft=max(nums1[i-1],nums2[j-1]);
                if((nums1.size()+nums2.size())%2==1) return maxleft;
                int minright=0;
                    if(i==nums1.size()) minright=nums2[j];
                    else if(j==nums2.size()) minright=nums1[i];
                    else minright=min(nums1[i],nums2[j]);
                    return (maxleft+minright)/2.0;
            }
        }
        return 0.0;
    }
};

说明

  • 本题难点在于O(log(m+n)),否则双指针或者组成新数组排序的方法都可以解决，不过时间复杂度都是O(m+n)

O(log(m+n))第一反应一般是二分查找

现在有两个数组A和B，分别由m和n的数(\(m,n\geq 0\)),假设我们在某位置切分A数组，使得A数组变为两部分各有i和m-i个数；以同样的方法在B数组进行切分，使得B数组变为两部分各有j和n-j个数。

要找到中位数，我们就要把A和B两个数组的分成这样的两部分，

  • i+j=m-i+n-j(m+n为偶数)或i+j=m-i+n-j+1(m+n为奇数) 这样保证左右两部分数组个数相等或相差1。
  • a[i-1]<=b[j]且b[j-1]<=a[i] 保证满足max(a,b左侧数组)>=min(a,b右侧数组)
  • a[i-1]>b[j]表示a数组左侧部分最大值过大，i值应该减小，左移imax最大值变为i-1
  • b[j-1]>a[i]表示b数组左侧部分最大值过大，j应该减小，即i应该增加，imin增大为i+1
  • i或j等于0时，maxleft就应该为b[j-1]或a[i-1]
  • i或j等于m或n时，minright应该为b[j]或a[i]