欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

4. 寻找两个有序数组的中位数

程序员文章站 2022-04-17 16:57:32
...

4. 寻找两个有序数组的中位数
解法一:暴力法
先将两个数组合并,然后根据奇数,还是偶数,返回中位数。时间复杂度不符合要求。
复杂度
时间复杂度:遍历全部数组O (m+n)
空间复杂度:开辟了一个数组,保存合并后的两个数组 O(m+n)

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m=nums1.size();
        int n=nums2.size();
        vector<int> res(m+n,0);
        if(n==0){
            if(m%2==0)
                return (nums1[m/2-1]+nums1[m/2])/2.0;
            else
                return nums1[m/2];
        }
        if(m==0){
            if(n%2==0)
                return (nums2[n/2-1]+nums2[n/2])/2.0;
            else
                return nums2[n/2];
        }
        int cnt=0,i=0,j=0;
        while(cnt!=(m+n)){
            if(i==m){
                while(j!=n)
                    res[cnt++]=nums2[j++];
                break;
            }
            if(j==n){
                while(i!=m)
                    res[cnt++]=nums1[i++];
                break;
            }
            if(nums1[i]<nums2[j])
                res[cnt++]=nums1[i++];
            else
                res[cnt++]=nums2[j++];
        }
        
        if(cnt%2==0)
            return (res[cnt/2-1]+res[cnt/2])/2.0;
        else
            return res[cnt/2];
    }
};

方法二:双指针

数组长度之和是奇数的时候,要看到索引为(m−1)/2的这个数,数组长度之和是偶数时要看到索引为m/2的这个数。有两种思路:
思路1(不采用):
不管长度之和是奇数还是偶数,直接先看到索引为(m−1)/2的这个数,如果是奇数,就可以返回了,如果是偶数,再往下看一个数;编码的时候,发现,会有一些冗余的代码,并且要考虑一些边界的问题,例如看索引为m/2的数的时候,可能 nums1 和 nums2 其中之一已经看完。
思路2(采用):那么不管奇数偶数,我都看到索引为m/2的这个数,那么索引为(m−1)/2 的这个数肯定看过了。
技巧:
1、我只关心最近看到的这两个数,那么我不妨将它们放置在一个长度为2的数组中,使用计数器模2的方式计算索引(这个技巧貌似叫做“滚动变量”),这样空间复杂度就可以降到常数。
2、在编码的时候,使用 counter 这个指针表示最后一次赋值的那个索引,初始化的时候,应该为-1,在每一次循环开始之前 ++。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m=nums1.size();
        int n=nums2.size();
        int mid=(m+n)>>1;   //中间的数的索引
        int cnt=-1,i=0,j=0;    //cnt为移动索引,i为nums1的索引,j为nums2的索引   
        int res[2]={0};      
        while(cnt<mid){
            cnt++;
            // 先写i和j遍历完成的情况,否则会出现数组下标越界
            if(i==m)
                res[cnt&1]=nums2[j++];
            else if(j==n)
                res[cnt&1]=nums1[i++];
            else if (nums1[i] < nums2[j])
                res[cnt&1] = nums1[i++];
            else 
                res[cnt&1] = nums2[j++];
        }
        // 如果 m + n 是奇数,mid就是我们要找的
        // 如果 m + n 是偶数,有一点麻烦,要考虑其中有一个用完的情况,其实也就是把上面循环的过程再进行一步
        if (((m+n)&1) == 1)
            return res[cnt&1];
        else
            return (double)(res[0]+res[1])/2;
        return -1;
    }
};

方法三:二分法

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
       //使nums1为短的数组,缩小查找范围
       if(nums1.size()>nums2.size())
           return findMedianSortedArrays(nums2,nums1);
        int m=nums1.size();     //在nums1的0~m中查找
        int n=nums2.size();
        int left=0,right=m;     //nums1的左右边界
        while(left<=right){
            int i=left+(right-left)/2;   //nums1的分界线
            int j=((m+n+1)>>1)-i;      //要保证左右数量一样,nums2的分界线可由nums1的分界线算出
            //处理边界情况
            int nums1LMax=i==0?INT_MIN:nums1[i-1];
            int nums1RMin=i==m?INT_MAX:nums1[i]; 
            int nums2LMax=j==0?INT_MIN:nums2[j-1];
            int nums2RMin=j==n?INT_MAX:nums2[j]; 
            if (nums1LMax <= nums2RMin && nums2LMax <= nums1RMin){    //找到
                if((m+n)%2) //总数奇数个
                    return max(nums1LMax,nums2LMax);
                else    //总数偶数个
                    return (max(nums1LMax, nums2LMax) + min(nums1RMin, nums2RMin))/2.0;
            }
            else if (nums2LMax > nums1RMin)
                left=i+1;	//左边界右移动
            else
                right=i-1;	//右边界左移动
        }
        return -1; //错误退出
    }
};
相关标签: leetcode