寻找两个正序数组的中位数

寻找两个正序数组的中位数

时隔许久，我又回来了。

题目：给定两个大小分别为m和n的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的中位数。
要求算法的时间复杂度为O(log(m+n))。

示例1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

题目链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

C++实现

方法一：
很朴素的想法，通过归并排序的思路将两个正序数组合并为一个数组data，再根据data所含个数的奇偶性分别返回相应的结果。
时间复杂度O(m+n)

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        //新开辟数组data，记录nums1和nums2合并后的有序数组
        vector<int> data;
        int i=0,j=0;
        while(i<nums1.size()&&j<nums2.size())
        {
            if(nums1[i]<nums2[j]){
                data.push_back(nums1[i++]);
            }
            else{
                data.push_back(nums2[j++]);
            }
        }
        while(i<nums1.size())
        {
            data.push_back(nums1[i++]);
        }
        while(j<nums2.size())
        {
            data.push_back(nums2[j++]);
        }
        double ret=0; //待返回的中位数
        if(data.size()%2==1)
        {
            ret=data[data.size()/2];
        }
        else{
            ret=(data[(data.size()-1)/2]+data[(data.size()-1)/2+1])/2.0;
        }
        return ret;
    }
};
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

方法二：
借鉴官方题解，通过二分查找实现。时间复杂度O(log(m+n))。
m+n是奇数时，中位数是两个正序数组中的第(m+n)/2+1个元素（从1开始数）；
m+n是偶数时，中位数是两个正序数组中的第(m+n)/2和第(m+n)/2+1个元素的平均值。

因此主要问题是实现找到两个正序数组的第k个元素的函数findKth()，如下所示：
使用index1和index2分别记录删除部分元素后，num1和num2下标的偏移量。初始为0。
比较num1[k/2-1]和num2[k/2-1]，以num1[k/2-1]<num2[k/2-1]为例，反之同理。num1[k/2-1]左侧共k/2-1个元素，即使num2[k/2-1]左侧的k/2-1个元素均全部小于num1[k/2-1]时，num1[k/2-1]名次取到最大为k-1，无法成为第k个元素。因此num1[k/2-1]及其左侧的元素均可排除，即nums1[0]到nums1[k/2-1]。k相应减少k/2个元素。
由于存在删除元素后考虑位置发生偏移，因此需要加上相应的基准index1和index2。
要注意可能存在index*+k/2-1下标越界的情况：nextIndex1=min(index1+k/2-1,m-1)。如果某一个数组越界，直接返回另一个数组中的第k个元素。

示例分析：
num1={1，3，4，9}
num2={1，2，3，4，5，6，7，8，9}
找第k=(4+9)/2+1=7个元素

index1=0，index2=0，比较下标为k/2-1=2的两个数：num1[2]=4>num2[2]=3，于是num2[index2]到num2[index2+k/2-1]范围内的元素被排除。修改index2和k：index2=3，k=k-k/2=4。index1=0。

比较num1[index1+k/2-1]=num1[1]和num2[index2+k/2-1]=num2[4]：num1[1]=3<num2[4]=5。于是num1[0]到num1[1]范围元素被排除。修改index1和k：index1=2，k=k-k/2=2。index2=3。

比较num1[index1+k/2-1]=num1[2]和num2[index2+k/2-1]=num2[3]：num1[2]=4<num2[3]=4。于是num1[2]到num1[2]范围元素被排除。修改index1和k：index1=3，k=k-k/2=1。index2=3。

k==1时，返回num1[index1]和num2[index2]中较小的一个，结束循环。这里返回4即为所求第7个数。

代码：

class Solution {
public:
    int findKth(vector<int>& nums1, vector<int>& nums2,int k) //找到两个正序数组的第k个元素
    {
        int m=nums1.size();
        int n=nums2.size();
        int index1=0,index2=0; //index1和index2分别记录num1和num2各自的偏移量
        while(1)
        {
        	//边界情况
            if(index1==m){return nums2[index2+k-1];} //num1越界
            if(index2==n){return nums1[index1+k-1];} //num2越界
            if(k==1){return min(nums1[index1],nums2[index2]);}
            //正常情况
            int nextIndex1=min(index1+k/2-1,m-1); //下一个比较值下标，注意越界时删除元素变少
            int nextIndex2=min(index2+k/2-1,n-1);
            if(nums1[nextIndex1]<=nums2[nextIndex2])
            {
                k-=(nextIndex1-index1+1); //修改k
                index1=nextIndex1+1; //删除num1中元素，修改index1
            }
            else{
                k-=(nextIndex2-index2+1); //修改k
                index2=nextIndex2+1; //删除num2中元素，修改index2
            }
        }
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m=nums1.size();
        int n=nums2.size();
        if((m+n)%2==1){return findKth(nums1,nums2,(m+n)/2+1);}
        else{return (findKth(nums1,nums2,(m+n)/2)+findKth(nums1,nums2,(m+n)/2+1))/2.0;}
    }
};
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