LeetCode——第四题（C++）：寻找两个有序数组的中位数

77 阅读 0 评论 51 点赞

我是靠谱客的博主机智红牛，最近开发中收集的这篇文章主要介绍LeetCode——第四题（C++）：寻找两个有序数组的中位数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

一些想法
1、定义L = Max(LeftPart)，R = Min(RightPart)，并且 Li<=Ri是肯定的（因为数组升序，左边肯定小于右边）
2、若割点刚好处于中间，此时只需要找到当L1<R2,L2<R1的时候，比较L1和L2的数值，找选出最大的（因为左半部分从左到右是依次增大，那么找出最靠近右边的那个数m1），再比较R1和R2的数值，找出最小的（因为右半部分从左到右依次增大，那么找出最靠近左边的那个数m2）。此时(m1+m2)/2便是要求的中位数。
3、如果 L1>R2，说明数组1的左边元素太大（多），我们把C1减小，把C2增大。L2>R1同理，把C1增大，C2减小。
4、由于m+n为奇偶处理方案不同，故可以让两个数组长度之和恒为奇数。虚拟加入‘#’，让数组长度恒为奇数（2n+1恒为奇数）。由于是虚拟加，所以其实根本没这一步，因为通过这个转换，我们可以保证虚拟加后每个元素跟原来的元素一一对应。加完之后，每个位置可以通过/2得到原来元素的位置。
5、如果C1或C2已经到头了
这种情况出现在有个数组完全小于或大于中值。
可能有4种情况：
C1 = 0 —— 数组1整体都比中值大，L1 >R2，中位数在数组2中
C2 = 0 —— 数组1整体都比中值小，L1 <R2，中位数在数组1中
C1=n* 2 —— 数组1整体都比中值小，L1 <R2，中位数在数组2中
C2 = m*2 —— 数组1整体都比中值大，L1 >R2，中位数在数组1中

则解决方案有：
如果C1 = 0 —> 那么我们缩小L1，L1 = INT_MIN，保证判断正确。
如果C1 = n*2 —> 那么我们增大R1，R1 = INT_MAX，保证判断正确。

运行成功的代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n=nums1.size();
        int m=nums2.size();
        if(n>m)//保证数组1一定最短
            return findMedianSortedArrays(nums2,nums1);
        int L1,L2,R1,R2,c1,c2,lo = 0, hi = 2*n;  //虚拟加了'#'所以数组1是2*n+1长度
        while(lo <= hi)   //二分
        {
            c1 = (lo+hi)/2;  //c1是二分的结果
            c2 = m+n- c1;
            L1 = (c1 == 0)?INT_MIN:nums1[(c1-1)/2];
            R1 = (c1 == 2*n)?INT_MAX:nums1[c1/2];
            L2 = (c2 == 0)?INT_MIN:nums2[(c2-1)/2];
            R2 = (c2 == 2*m)?INT_MAX:nums2[c2/2];
           if(L1 > R2)
                hi = c1-1;
            else if(L2 > R1)
                lo = c1+1;
            else
                break;
        }
        return (max(L1,L2)+ min(R1,R2))/2.0;
    }
};

在这里插入图片描述