两个排序数组的中位数

发表于 | 分类于 | 阅读次数：
本文字数： 2k | 阅读时长 ≈ 5 分钟

问题提出

#4 Median of Two Sorted Arrays

如何在对数时间复杂度内找出两个有序数组的中位数？

算法

二分递归

设两个有序列表为nums1和nums2，要想找到其中位数，思路在于找到一个划分，将nums1和nums2都分为两部分：

1
2
3
4
nums1_left  -> nums1[0], nums1[1], ... , nums1[i-1]
nums1_right -> nums1[i], nums1[i+1], ... , nums1[m]
nums2_left  -> nums2[0], nums2[1], ... , nums2[j-1]
nums1_right -> nums2[j], nums2[j+1], ... , nums2[n]

且使得：

1
2
3
4
5
M -> nums1_left + nums2_left
N -> nums1_right + nums2_right
// when (m+n) is even
len(M) == len(N)
max(M) <= min(N)

易得，中位数即为Max(M)或(Max(M)+Min(N))/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
38
39
40
#include <iostream>
#include <vector>
using namespace std;

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
	int m = nums1.size(), n = nums2.size();
	if (m > n) {
		vector<int> temp1 = nums1; nums1 = nums2; nums2 = temp1;
		int temp2 = m; m = n; n = temp2;
	}
	int begin = 0, end = m;
	while (begin <= end) {
		int i = (end + begin) / 2;
		int j = (m + n + 1) / 2 - i;
		if (i < end && nums1[i] < nums2[j - 1]) { begin = i + 1; }
		else if (i > begin && nums1[i - 1] > nums2[j]) { end = i - 1; }
		else {
			int maxLeft = 0;
			if (i == 0) { maxLeft = nums2[j - 1]; }
			else if (j == 0) { maxLeft = nums1[i - 1]; }
			else { maxLeft = (nums1[i - 1] > nums2[j - 1]) ? nums1[i - 1] : nums2[j - 1]; }
			if ((m + n) % 2 == 1) return maxLeft;

			int minRight = 0;
			if (i == m) { minRight = nums2[j]; }
			else if (j == n) { minRight = nums1[i]; }
			else { minRight = (nums1[i] < nums2[j]) ? nums1[i] : nums2[j]; }
			return (maxLeft / 2.0 + minRight / 2.0);
		}
	}
	return 0.0;
}

int main() {
	vector<int> nums1 = {1, 2};
	vector<int> nums2 = {-1, 3};
	double ret = findMedianSortedArrays(nums1, nums2);
	cout << ret << endl;
	return 0;
}

总结

hard难度做不来。。。