这是LeetCode的第四题

题目

这道题的要求是找出数组长度为m和n的两个有序数组nums1和nums2的中位数.m和n不同时等于0.

并且要求算法复杂度为O(log(m+n))

题解

根据题目要求我们不难看出这道题应该用二分查找来解决.题目中要求找中位数.


\[left\_part= left\_part(nums1)+left\_part(nums2)\\right\_part=right\_part(nums1)+right\_part(nums2)\]
于是题目等价于找到

\[ \mbox{当m+n为偶数时, }len(left\_part)=len(right\_part)\\\mbox{当m+n为奇数时, }len(left\_part)=len(right\_part)+1\\max(left\_part)\leqq min(right\_part)\]

即,确定游标\(i\)\(j\)的值,将\(nums1\)\(nums2\)分别划分成符合上式的两个部分

我们可以假定\(m\leqq n\)(如果m>n,可以调换nums1和nums2)
\[half\_len:=len(left\_part)=\frac{m+n+1}{2}\tag{1}\]
现在我们来讨论一下游标的含义.
使用\(i\)\(j\)\(nums1\)\(nums2\)分成两个部分,由于数组下标从0开始,所以nums1[i]的有如下含义:

\[i = len(left\_part(nums1))\Rightarrow i\in [0,m]\tag{2}\]

当然,\(nums1[m]\)并不存在,在这里我们假定有一个\(nums1[m]\),但实际上我们不会访问到\(nums1[m]\)中的值.

\(nums1[m]\)作为哨兵,这样可以省去讨论边界条件的麻烦.当\(i=m\)时表明\(nums1\)中所有元素属于\(left\_part(nums1)\)




\[j = len(left\_part(nums2))=half\_len-i\tag{3}\\\mbox{由(1)和(2)可得}\\j = \frac{m+n+1}{2}-i\]

由于m和n都是已知,并且\(j\)可以由\(i\)推导出.

综上,此题就转化成了在\(nums1\)中找\(i\)的问题.

最高效的方法就是使用二分查找来找\(i\),初始条件为:
\[begin = 0\\end = m\\i = \frac{begin+end}{2}\]
找到\(nums[i]\)后,可以分成以下三种情况

  • \(i>0,nums1[i-1]>nums2[j]\Rightarrow i\mbox{太大}\),在\([begin,i)\)内搜索
  • \(i<m,nums1[i]<nums2[j-1]\Rightarrow i\mbox{太小}\),在\((i,end]\)内搜索
  • 若上述两种情况都不成立,\(i\)符合条件,搜索停止

此时我们得到了\(i\)符合划分要求,接下来就是找中位数

  • 如果m+n为奇数,那么中位数为\(max(left\_part)\)
  • 如果m+n为偶数,那么中位数为\(\frac{max(left\_part)+min(right\_part)}{2}\)

关于\(max(left\_part)\)的求解,

  • 如果\(i=0\),那么可知\(max(left\_part)=nums2[j-1]\)
  • 如果\(j=0\),那么可知\(max(left\_part)=nums1[i-1]\)
  • 一般情况,\(max(left\_part)=max(nums1[i-1],nums2[j-1])\)

同理可获得\(min(right\_part)\)

复杂度分析

  • 计算复杂度: \(O(\log(max(m,n)))\)
  • 空间复杂度:\(O(1)\)

实现代码

class Solution {
    public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if(m>n) // 确保m>n
        {
            return findMedianSortedArrays(nums2, nums1);
        }
        int halfLen = (m+n+1)/2;
        int i,j,begin = 0,end= m;
        double rval= 0.0;
        while(begin<=end)
        {
            i = (begin+end)/2;
            j = halfLen-i;
            if(i<m&&nums1[i]<nums2[j-1])
            {
                begin = i+1;
            }
            else if(i>0&&nums1[i-1]>nums2[j])
            {
                end = i-1;
            }
            else
            {
                int maxLeft,minRight;
                if(i==0){
                    maxLeft = nums2[j-1];
                }else if (j==0)
                {
                    maxLeft = nums1[i-1];
                }else{
                    maxLeft = nums1[i-1]>nums2[j-1]?nums1[i-1]:nums2[j-1];
                }
                if((m+n)%2==1)
                {
                    rval = maxLeft;
                    break;
                }
                if(i==m)
                {
                    minRight = nums2[j];
                }else if (j==n)
                {
                    minRight = nums1[i];
                }else
                {
                    minRight = nums1[i]<nums2[j]?nums1[i]:nums2[j];
                }
                rval = ((double)(maxLeft+minRight))/2;
                break;
            }
        }
        return rval;
    }
};
12-29 14:32