C++力扣4 寻找两个正序数组的中位数（困难）

125 阅读 0 评论 83 点赞

我是靠谱客的博主谦让萝莉，这篇文章主要介绍C++力扣4 寻找两个正序数组的中位数（困难），现在分享给大家，希望可以做个参考。

输入：nums1=[1, 2]，nums2=[3, 4]

输出：2.5

题意：找出两个正序数组合并在一起的中位数，要求时间复杂度为O(m+n)，m、n为两个数组的长度。

1、自己做的

先合并两个vector，再找出中位数。但是合并排序的复杂度是O(nlogn)，不合题意。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        double result;
        vector<int> nums3;
        nums3.resize(nums1.size()+nums2.size());
        // 1、合并两个vector
        merge(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), nums3.begin());
        // 2、找中位数
        if(nums3.size() % 2 == 0){
            result = (nums3[nums3.size()/2] + nums3[(nums3.size()+1)/2])/2.0;
        }else{
            result = nums3[nums3.size()/2];
        }
        return result;
    }
};

2、非官方题解

复制代码

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
35
36
37
#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;
	}
};