专栏首页Michael阿明学习之路LeetCode 4. 寻找两个有序数组的中位数(二分查找,难)

LeetCode 4. 寻找两个有序数组的中位数(二分查找,难)

1. 题目

给定两个大小为 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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

2.1 合并数组

  • 合并两个数组,再取中位数
  • 时间和空间复杂度均为 O(m+n)
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    	int n1 = nums1.size(), n2 = nums2.size(), len;
    	len = n1 + n2;
        vector<int> nv(len);
        int i = 0, j = 0, k = 0;
        while(i < n1 && j < n2)
        {
        	if(nums1[i] < nums2[j])
        		nv[k++] = nums1[i++];
        	else
        		nv[k++] = nums2[j++];
        }
        if(i == n1)
        {
        	while(j < n2)
        		nv[k++] = nums2[j++];
        }
        else
        {
        	while(i < n1)
        		nv[k++] = nums1[i++];
        }
        if(len%2)
        	return nv[len/2];
        return (nv[len/2]+nv[len/2-1])/2.0;
    }
};

2.2 优化2.1解法,双指针

  • 不合并两个数组,设置双指针在两个数组上
  • 比较大小,分别移动各自的指针,遍历到中间的计数停止
  • 时间复杂度 O(m+n),空间复杂度 O(1)
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    	int n1 = nums1.size(), n2 = nums2.size(), len;
    	len = n1 + n2;
        vector<int> nv(len);
        int i = 0, j = 0, k, left = -1, right = -1;
        for(k = 0; k <= len/2; ++k)
        {
        	left = right;
        	if(i < n1 && (j >= n2 || nums1[i] < nums2[j]))
        		right = nums1[i++];
        	else
        		right = nums2[j++];
        }
        if(len%2)
        	return right;
        return (left+right)/2.0;        
    }
};

2.3 二分法(找第k个数)

参考链接,解法3

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    	int n1 = nums1.size(), n2 = nums2.size(), len, kth;
    	len = n1 + n2;
    	kth = (len+1)/2;
    	if(len%2)
    		return findKth(nums1,0,n1-1,nums2,0,n2-1,kth);
    	return (findKth(nums1,0,n1-1,nums2,0,n2-1,kth)+findKth(nums1,0,n1-1,nums2,0,n2-1,kth+1))/2.0;      
    }

    int findKth(vector<int>& nums1, int s1, int e1, vector<int>& nums2, int s2, int e2, int kth)
    {
    	int len1 = e1-s1+1;
    	int len2 = e2-s2+1;
    	if(len1 > len2)	//确保传进来的参数len1是较短的数组(它先空)
    		return findKth(nums2,s2,e2,nums1,s1,e1,kth);
    	if(len1 == 0)
    		return nums2[s2+kth-1];//一个为空,直接找到答案
    	if(kth == 1)
    		return min(nums1[s1],nums2[s2]);
    	int i = s1+min(len1,kth/2)-1;//min使得指针不会越界
    	int j = s2+min(len2,kth/2)-1;
    	if(nums1[i] > nums2[j])//舍去nums2前面的
    		return findKth(nums1,s1,e1,nums2,j+1,e2,kth-(j-s2+1));
    	else//舍去nums1前面的
    		return findKth(nums1,i+1,e1,nums2,s2,e2,kth-(i-s1+1));
    }
};
O(lg(m+n))

时间复杂度,尾递归,无需堆栈,空间复杂度

O(1)

2.4 切分法

  • 放了方便处理,确保A数组长度较短
  • 初始状态下mid1取数组1的中间,mid1,mid2左半边的总个数 == 右半边 或者 比右半边少1
  • 对mid1进行二分查找,相应的mid2会随动(
mid2 = allHalf - mid1

  • 如果
lmax1 <= rmin2 ,\quad and \quad lmax2 <= rmin1

, 成功找到分界线

Lmax = max(lmax1,lmax2))

,

Rmin = min(rmin1, rmin2)

,总个数为奇数返回

Rmin

, 偶数返回

(Lmax+Rmin)/2.0
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        if(n1 > n2)//确保n1是较短的数组
            return findMedianSortedArrays(nums2, nums1);
        int left = 0, right = n1, allHalf = (n1+n2)/2, mid1, mid2;
        int lmax1, rmin1, lmax2, rmin2;
        while(left <= right)
        {
            mid1 = left+((right-left)>>1);
            mid2 = allHalf - mid1;
            lmax1 = (mid1-1 >= 0) ? nums1[mid1-1] : INT_MIN;
            rmin1 = (mid1 < n1) ? nums1[mid1] : INT_MAX;
            lmax2 = (mid2-1 >= 0) ? nums2[mid2-1] : INT_MIN;
            rmin2 = (mid2 < n2) ? nums2[mid2] : INT_MAX;
			//在边界处,认为没有元素,设置成最大或者最小,保证下面关系式成立
            if(lmax1 > rmin2)
                right = mid1-1;
            else if(lmax2 > rmin1)
                left = mid1+1;
            else
            {
                left = right = mid1;
                break;
            }
        }
        int i = left, j = allHalf-left;
        int l = max(
                    i-1 >= 0 ? nums1[i-1] : INT_MIN,
                    j-1 >= 0 ? nums2[j-1] : INT_MIN);
        int r = min(
                    i < n1 ? nums1[i] : INT_MAX,
                    j < n2 ? nums2[j] : INT_MAX);
        if((n1+n2)%2 == 1)
            return r;
        return (l+r)/2.0;
    }  
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 350. 两个数组的交集 II(哈希)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/intersection-of-two-arrays-...

    Michael阿明
  • LeetCode 496. 下一个更大元素 I(哈希)

    给定两个没有重复元素的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的...

    Michael阿明
  • LeetCode 1458. 两个子序列的最大点积(动态规划,类似编辑距离)

    数组的非空子序列是通过删除原数组中某些元素(可能一个也不删除)后剩余数字组成的序列,但不能改变数字间相对顺序。 比方说,[2,3,5] 是 [1,2,3,4,...

    Michael阿明
  • LeetCode100|两个数组的交集II

    这是自己目前输出的leetcode第100篇题解慢一点,才能更快,98道leetcode,也是自己坚持过程中一个结果,感谢周围的人和自己,这里道一句谢谢吧,没有...

    码农王同学
  • 两个数组的交集 II

    就相当于是数学集合求交集,很容易想到的就是双指针扫描比较判断是否存入结果。对于这样的方式就选择先排序再比较。

    木瓜煲鸡脚
  • 【leetcode刷题】T43-两个数组的交集

    Given two arrays, write a function to compute their intersection.

    木又AI帮
  • 第K小数——折半删除

    给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

    MickyInvQ
  • Merge Sorted Array

    Tyan
  • LeetCode 349. Intersection of Two Arrays题目代码代码

    样例 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2].

    desperate633
  • 【leetcode 简单】 第八十五题

    py3study

扫码关注云+社区

领取腾讯云代金券