地址

https://leetcode.com/problems/median-of-two-sorted-arrays/description/

题目

Median of Two Sorted Arrays

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

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

题解

看题目时间复杂度可以知道这题是要在两个数组间进行二分。
假设选定i和j满足$i+j=k$，k代表中位数的位置。
如果$a[i]<=b[j]$，则中位数不在a数组前i个数中，删除a数列前i个数。反之$a[i]>b[j]$,同理。证明方法 反证法，自己想想就知道了。
当然删除不是真的删除，打个标记而已，不然时间复杂度炸了。

ps：好久没做题了，想到思路后还写了好久，然后又debug好久，真是丢人。代码写的真是丑陋。

代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
        int n=a.size(),m=b.size(),c=(n+m)&1,k=(n+m+1)/2;
        int sa=-1,sb=-1;
        n--,m--;
        while(1)
        {
            if(sa==n&&c)
                return b[sb+k]*1.0;
            else if(sa==n)
                return (b[sb+k]+b[sb+k+1])/2.0;
            if(sb==m&&c)
                return a[sa+k]*1.0;
            else if(sb==m)
                return (a[sa+k]+a[sa+k+1])/2.0;
            if(k==1)
            {
                if(c)
                    return min(a[sa+1],b[sb+1])*1.0;
                else
                {
                    if(a[sa+1]<b[sb+1])
                    {
                        if(sa+2<=n)
                            return (min(a[sa+2],b[sb+1])+a[sa+1])/2.0;
                        else
                            return (a[sa+1]+b[sb+1])/2.0;
                    }
                    else
                    {
                        if(sb+2<=m)
                            return (min(a[sa+1],b[sb+2])+b[sb+1])/2.0;
                        return (a[sa+1]+b[sb+1])/2.0;
                    }
                }
            }
            int i=min(k/2,n-sa),j=k-i;
            if(j>m-sb)
                j=m-sb,i=k-j;
            if(a[sa+i]<=b[sb+j])
                k-=i,sa+=i;
            else
                k-=j,sb+=j;
        }
        
    }
};