Leetcode-4 Median of Two Sorted Arrays

发表于 | 分类于 | 次

Median of Two Sorted Arrays

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

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

解题思路

将两个数组分别分割为左右两部分，二者左边元素数量之和应该为总数量的一半。若左边元素都小于等于右边元素，即nums1中左边最大元素小于等于nums2中右边最小元素且nums2中左边最大元素小于等于nums1中右边最小元素，则中位数能够由这四个元素产生。若不满足，需要将nums1中的分割点向左或向右移动。

复杂度分析

  • 时间复杂度：$O(min(m,n))$，最坏情况下需要移动半个数组
  • 空间复杂度：$O(1)$

代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <iostream>

using namespace std;

class Solution_4 {
public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		int m = nums1.size(), n = nums2.size();
		if (m > n) { //移动短数组,降低移动次数
			swap(nums1, nums2);
			swap(m, n);
		}
		int l = m + n; //总共有多少个元素
		int lmxi = m / 2 - 1, rmxi = m / 2; //nums1中 左边最大/右边最小 元素索引
		int lmyi, rmyi;         //nums2中 左边最大/右边最小 元素索引
		int lmx, lmy, rmx, rmy; //nums1和nums2中 左边最大/右边最小 元素

		//当nums1全部元素位于同一边,一定能得到中位数,但需要更新nums2的分割点
		while (lmxi >= -1 && rmxi <= m) {
			//nums1和nums2中的左边元素数量之和应该为总数量的一半: l/2
			//nums1中左边元素个数为rmxi,nums2中左边元素个数为l/2-rmxi,最后元素的索引等于数量减一
			lmyi = l / 2 - rmxi - 1;
			rmyi = lmyi + 1;

			lmx = lmxi < 0 ? INT_MIN : nums1[lmxi];
			rmx = rmxi >= m ? INT_MAX : nums1[rmxi];
			lmy = lmyi < 0 ? INT_MIN : nums2[lmyi];
			rmy = rmyi >= n ? INT_MAX : nums2[rmyi];

			//nums1和nums2中的所有左边元素都不大于右边元素,且正好分成两半
			//中位数由分界处的四个元素产生
			if (lmx <= rmy && lmy <= rmx) {
				if (l % 2)return min(rmx, rmy);
				return (max(lmx, lmy) + min(rmx, rmy)) / 2.0;
			}
			else if (lmx > rmy) {
				lmxi--; //nums1中左边最大元素大于nums2中右边最小元素,应该使其降低,即向左移动
			}
			else if (lmy > rmx) {
				lmxi++; //nums1中右边最小元素小于nums2中左边最大元素,应该使其增加,即向右移动
			}
			rmxi = lmxi + 1;
		}
	}
};

void test_4()
{
	vector<int> a = { 1 }, b = { 2,3 };
	std::cout << (Solution_4().findMedianSortedArrays(a, b) == 2) << endl;
}

改进

在移动分割点时，采用二分法确定位置，使算法的时间复杂度降低到：$O(log(min(m,n)))$

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
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
	int m = nums1.size(), n = nums2.size();
	if (m > n) { //选择短数组,降低二分次数
		return findMedianSortedArrays(nums2, nums1);
	}
	int l = m + n;          //总共有多少个元素
	int lmx, rmx, lmy, rmy; //nums1(nums2)中`左边最大和右边最小`元素
	int px, py;             //nums1和nums2的分割点, >=px(py) 划为右边

	int low = 0, high = m;  //用于二分搜索
	while (low <= high) {
		px = (low + high) / 2;
		py = l / 2 - px;

		lmx = px == 0 ? INT_MIN : nums1[px - 1];
		rmx = px == m ? INT_MAX : nums1[px];
		lmy = py == 0 ? INT_MIN : nums2[py - 1];
		rmy = py == n ? INT_MAX : nums2[py];

		//所有元素等分两半,且左边元素都不大于右边元素,则中位数由分界点的四个元素产生
		if (lmx <= rmy && lmy <= rmx) {
			if (l % 2) return min(rmx, rmy);
			return (max(lmx, lmy) + min(rmx, rmy)) / 2.0;
		}
		else if (lmx > rmy) {
			high = px - 1; //nums1中左边最大元素大于nums2中右边最小元素,应该使其减小,选择左边
		}
		else if (lmy > rmx) {
			low = px + 1;  //nums1中右边最小元素小于nums2中左边最大元素,应该使其增大,选择右边
		}
	}
}