Joyce' Blog
0%

median-of-two-sorted-arrays

发表于 更新于

Description

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
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

思路

对于复杂度的要求加大了题目的难度，一般容易想到线性级别的解决方法，如果要降到对数级别，要用到二分查找法。这里的二分其实是针对切割的位置。参考了LeetCode上的解答。

https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2471/very-concise-ologminmn-iterative-solution-with-detailed-explanation

为了简化问题，偶数和奇数个数的有序数组，可以综合成一种情况：数组长度为N时，index of L = (N-1)/2, and R is at N/2。 中位数的下标可以表示为(L + R)/2 = (A[(N-1)/2] + A[N/2])/2。函数中使A1是更长的数组。

设想数组中有更多的位置：

1
2
A1: [# 1 # 2 # 3 # 4 # 5 #]    (N1 = 5, N1_positions = 11)
A2: [# 1 # 1 # 1 # 1 #]     (N2 = 4, N2_positions = 9)

两个数组共有2N1 + 2N2 + 2个位置，每次分割后左右分别有N1 + N2个位置，最终的分割应保证L1 <= R1 && L1 <= R2 && L2 <= R1 && L2 <= R2，相当于L1 <= R2&&L2 <= R1。

在两种情况下需要对切割的位置做出调整：

  • L1>R2：说明A1左边大数过多，A1的切割点左移，同时A2切割点右移；

  • L2>R1：说明A2左边大数过多，A2的切割点左移，同时A1切割点右移；

    否则，找到的即为中位数的位置，中位数等于(max(L1, L2) + min(R1, R2)) / 2。

C++代码

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
#include<iostream>
#include<vector>
using namespace std;
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
{
	int m = nums1.size();
	int n = nums2.size();
	if (m < n)
		return findMedianSortedArrays(nums2, nums1);

	int lo = 0, hi = n * 2;
	while (lo <= hi)
	{//移动A2的切割点，A2为长度更短的数组
		int c2 = (lo + hi) / 2;
		int c1 = m + n - c2;

		double L1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
		double L2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
		double R1 = (c1 == m*2) ? INT_MAX : nums1[(c1) / 2];
		double R2 = (c2 == n*2) ? INT_MAX : nums2[(c2) / 2];

		if (L1 > R2) lo = c2 + 1;
		else if (L2 > R1)hi = c2 - 1;
		else
			return (((L1> L2)?L1:L2) + ((R1<R2)?R1:R2)) / 2.0;
	}
	return -1;
}
int main()
{
	vector<int> nums1;
	vector<int> nums2;
	for (int i = 0; i < 6; i++)
	{
		cout << i * 2 << " ";
		nums1.push_back(i * 2);
	}
	cout << endl;
	for (int j = 0; j < 9; j++)
	{
		cout << j * j << " ";
		nums2.push_back(j*j);
	}
	cout << endl;
	double a=findMedianSortedArrays(nums1, nums2);
	cout << a << endl;
	return 0;
}

分析

复杂度：O(log(min(N1, N2)))

若下标超出数组界限，可以假设有两个额外的值 INT_MAX at A[-1] 和 INT_MAX at A[N]，不影响结果并且简化了情况。