⚔ LeetCode | 4. Median of Two Sorted Arrays

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

Problem

LeetCode 4. Median of Two Sorted Arrays

Difficulty : Hard

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

Analysis

这道题需要在两个数组中找出中位数，看上去是并没有什么难度，最简单的办法就是将两个数组排序后直接取中位数位置上的值，但是这样做的话复杂度并不能达到O(log(m+n))。因此，我们需要寻找复杂度较低的算法。

首先，我想到的是先确定中位数的位置。

根据两个数组的长度，可以得出：

  • 当元素总个数为奇数时，下标为(m + n - 1) / 2的元素为中位数
  • 当元素总个数为偶数时，下标为(m + n) / 2 - 1的元素与下标为(m + n) / 2的元素的平均值为中位数

因此，算法的主要任务就是找出这一(两)个数

Approach 1 (伪)

一开始的思路是从一端开始遍历这两个数组，这里从开头开始遍历，使用两个变量i, j指向两个数组里面的元素。

每次遍历时：

当i和j都在数组范围之内时，将比较小的元素所在的数组的变量增加。

当i或j不在其数组范围时，将另一个变量增加

当算法执行k次后，自然就找到数组中第k大的元素，这样一来，就可以找到其中位数。

代码如下：

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
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	count := len(nums1) + len(nums2)
	one, two, i, j := 0, 0, 0, 0
	for k := 0; k <= count/2; k++ {
		if j >= len(nums2) || (i < len(nums1) && nums1[i] < nums2[j]) {
			if k == count/2-1 {
				one = nums1[i]
			} else if k == count/2 {
				two = nums1[i]
			}
			i++
		} else {
			if k == count/2-1 {
				one = nums2[j]
			} else if k == count/2 {
				two = nums2[j]
			}
			j++
		}
	}
	if count%2 == 0 {
		return float64(one+two) / 2
	}
	return float64(two)
}

但是这个算法的复杂度是O(m+n)的，并不符合题目所要求的O(log(m+n))， 因此还要继续寻找复杂度更低的算法。

Approach 2

上面的算法是从一端开始寻找这个中位数的，这里可以改进一下，从一开始就从中间去寻找这个中位数，再根据当前情况来将所寻找的位置前移或后移

首先，来看看一个数组里面的情况

当数组的长度为偶数的时候：

先把数组划分为两个部分

A[0], ..., A[i - 1] || A[i], ..., A[n - 1]

使得这两部分的元素的数量相同(i == n - i)，此时，(A[i] + A[i - 1]) / 2就是中位数，

这两部分中，后者的最小值需要大于前者的最大值，因此可以得到以下两个结论：

  • len(left_part) == len(right_part)
  • max(left_part) < min(right_part)

然后，把这个规律扩展到两个数组的时候

同样把数组划分成两个部分

A[0], ..., A[i - 1] || A[i], ... , A[m - 1]

B[0], ..., B[j - 1] || B[j], ... , B[n - 1]

并且左右两个部分满足上面两个条件，即：

  • i + j == m - i + n - j == j = (n + m) / 2 - i (0 <= i <= m )

  • max(A[i - 1], B[j - 1]) < min (A[i], B[j])

这里的j是通过i计算出来的，因此需要确保j是非负数，因此需要保证n > m。

此时，中位数就是 [max(A[i - 1], B[j - 1]) + min (A[i], B[j])] / 2

在两个数组的元素数量总和为奇数的时候，自然就没办法将数组划分为相等的两部分，因此需要统一将多出来的一个元素放到左边或者右边，当统一左边部分比右边部分多一个的时候j的表达式为j = (n + m + 1) / 2 - i。

此时，中位数就是max(A[i - 1], B[j - 1])

这样一来，算法的核心就变成如何快速找到一个i，满足上面的条件。

因为i的取值范围是0 <= i <= m , 因此比较好的方案就是取其取值范围的中间值，然后判断是否满足条件，调整取值范围然后再次找中间值。

因此可以根据以下的步骤快速找到i的值：

  1. 确保n > m, 如果不满足则将两个数组交换过来

  2. 确定搜索的范围，令iMin = 0,iMax = m

  3. 使得i = (iMin + iMax) / 2,j = (n + m + 1) / 2 - i

    • 如果i的取值范围内的元素只剩下一个，那么就说明当前值是符合要求的，跳到下一步
    • 如果 B[j - 1] <= A [i] && A[i - 1] <= B [j], 那么就可以判断左边部分的最大值小于右边部分的最小值，跳到下一步
    • 如果 B[j - 1] > A [i]， 那么说明满足要求的i比当前值要大，因此可以将搜索范围的下界设置为i + 1，即 iMin = i + 1， 然后跳转到第 3 步再次搜索
    • 如果 A[i - 1] > B [j]， 那么说明满足要求的i比当前值要小，因此可以将搜索范围的上界设置为i - 1，即 iMax = i - 1， 然后跳转到第 3 步再次搜索

  5. 确定i的值为当前值

至此，根据得到的i和j， 已经成功将两个数组划分为两个部分。

A[0], ..., A[i - 1] || A[i], ... , A[m - 1]

B[0], ..., B[j - 1] || B[j], ... , B[n - 1]

最后，对于一些特殊情况，比如i和j在两个数组的边界之中，还需要额外处理一下，

当两个数据的元素个数和为奇数的时候：

在一般情况下中位数就是max(A[i - 1], B[j - 1])

因为需要保证分组满足上面两个条件，同时需要保证数组的下标不会越界，因此

  • 当i = 0的时候，A[i - 1]是不存在的，可以看作A整个数组都在右边的部分，因此中位数取另一个数B[j - 1]
  • 当j = 0的时候，同样的情况，中位数取A[i - 1]

当两个数据的元素个数和为偶数的时候：

当i = m的时候：

在一般情况下中位数取[max(A[i - 1], B[j - 1]) + min (A[i], B[j])] / 2

max(A[i - 1], B[j - 1]) 这个我们可以通过上面奇数情况上的计算的结果，同时需要考虑min (A[i], B[j])越界的情况：

  • 当i = m的时候， A[i]是不存在的，因此可以看作A整个数组都在左边的部分，因此右边的部分的值可以取B[j]

  • 当j = n的时候，同理右边部分的值取A[i]

现在来分析一下具体的情况：

例：

A = [1, 5]

B = [2, 3, 4, 6]

因此i的搜索范围是[0, 2]，取中间值为 1

此时j = (2 + 4 + 1）/ 2 - 1 = 2

因此可以划分为

Left Right
1 5
2, 3 4, 5

显然左边的最大值小于右边的最小值，已经条件，因此可以确定i = 1

左边部分的数可以最大值 3，右边的数取最小值 4，因此中位数为(3 + 4) / 2 = 3.5

代码如下：

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
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	m := len(nums1)
	n := len(nums2)
	// make sure n > m
	if m > n {
		nums1, nums2 = nums2, nums1
		m, n = n, m
	}
	iMin, iMax := 0, m
	for iMin <= iMax {
		i := (iMin + iMax) / 2
		j := (m + n + 1) / 2 - i
		if i < iMax && nums2[j-1] > nums1[i] {
			iMin = i + 1
		} else if i > iMin && nums1[i-1] > nums2[j] {
			iMax = i - 1
		} else {
			left, right := 0, 0
			if i == 0 {
				left = nums2[j-1]
			} else if j == 0 {
				left = nums1[i-1]
			} else {
				left = int(math.Max(float64(nums1[i-1]), float64(nums2[j-1])))
			}
			if (m+n)%2 == 1 {
				return float64(left)
			}
			if i == m {
				right = nums2[j]
			} else if j == n {
				right = nums1[i]
			} else {
				right =int(math.Min(float64(nums2[j]), float64(nums1[i])))
			}
			return float64(left + right) / 2.0
		}
	}
	return 0.0
}

这种算法的搜索范围一开始是 0 到 m，然后一直对半地缩小搜索范围，有点类似二分法的思想，因此他的复杂度仅仅为O(log(min(m, n)))， 显然已经达到了题目所要求的O(log (m+n)).

Summary

这道题要找出答案并不难，难点在于如果在O(log (m+n))的复杂度下找出答案，主要是运用了中位数的基本定义以及二分法的思想，将复杂度降低为O(log(min(m, n)))。

土豪通道
0%