【LeetCode】4. Median of Two Sorted Arrays

韩旭051

发布于 2019-11-08 12:08:37

4120

发布于 2019-11-08 12:08:37

文章被收录于专栏：刷题笔记

本文链接：https://blog.csdn.net/shiliang97/article/details/101482613

英文原题

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

You may assume nums1 and nums2 cannot be both empty.

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

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

中文翻译

给定两个大小为 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解析看这个讲的很详细

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/4-xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu/

c++

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        if (n > m)return findMedianSortedArrays(nums2, nums1);//传参小大数组
        int start_pos = 0;//起点
        int end_pos = 2 * n;//终点
        int LMax1=0, RMin1=0, LMax2=0, RMin2=0;
        while(start_pos <= end_pos)//没有找到中位数就一直循环
        {
            int c1 = (start_pos + end_pos) / 2;//中间数的下标
            int c2 = m + n - c1;//剩下的位置
            LMax1 = c1> 0 ? nums1[(c1-1)/2] : INT_MIN;//赋值并判断
            RMin1 = c1 < 2 * n ? nums1[c1/2] : INT_MAX;
            LMax2 = c2 > 0 ? nums2[(c2-1)/2] : INT_MIN;
            RMin2 = c2 < 2 * m ? nums2[c2/2] : INT_MAX;
            if (LMax1 > RMin2)end_pos = c1 - 1;
            else if(LMax2 > RMin1)start_pos = c1 + 1;
            else break;
        }
        return (max<long>(LMax1, LMax2) + min<long>(RMin1, RMin2)) / 2.0;//返回中间那个值
    }
};

#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
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);
		}

		// Ci 为第i个数组的割,比如C1为2时表示第1个数组只有2个元素。LMaxi为第i个数组割后的左元素。RMini为第i个数组割后的右元素。
		int LMax1, LMax2, RMin1, RMin2, c1, c2, lo = 0, hi = 2 * n;  //我们目前是虚拟加了'#'所以数组1是2*n长度

		while (lo <= hi)   //二分
		{
			c1 = (lo + hi) / 2;  //c1是二分的结果
			c2 = m + n - c1;

			LMax1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
			RMin1 = (c1 == 2 * n) ? INT_MAX : nums1[c1 / 2];
			LMax2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
			RMin2 = (c2 == 2 * m) ? INT_MAX : nums2[c2 / 2];

			if (LMax1 > RMin2)
				hi = c1 - 1;
			else if (LMax2 > RMin1)
				lo = c1 + 1;
			else
				break;
		}
		return (max(LMax1, LMax2) + min(RMin1, RMin2)) / 2.0;
	}
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/09/26 ，如有侵权请联系 cloudcommunity@tencent.com 删除

https