找出两个有序数组的中位数

题目

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

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

则中位数是 2.0
1
2
3
4

示例 2:

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

则中位数是 (2 + 3)/2 = 2.5
1
2
3
4

中位数

先解释下一下中位数。

中位数(Median)又称中值,统计学中的专有名词,是按顺序排列的一组数据中居于中间位置的数,可将数值集合划分为相等的上下两部分, 即在这组数据中,有一半的数据比他大,有一半的数据比他小 。

二分查找

编程思路为:

题目要求的时间复杂度为 O(log(m+n)),是使用二分法的典型复杂度。其实该方案的时间复杂度会是 O(log(min(m, n))) 因为我们对其中一个长度较短的数组做 二分查找即可(但这两个时间复杂度的描述差不多没有本质区别)。

核心问题在于判断当前的分割位置是否是将数据分为左右相等,一半小,一半大的序列。判断依据是***若满足数组1左边最大的元素小于数组2右边最小的元素 同时 数组2左边最大的元素小于数组1右边最小的元素***,那么说明分割正确。

步骤如下:

  1. 确定长度较短的数组,进行二分。
  2. 从数组中间进行分割,然后确定当前的分割标准是否满足中位数标准。
  3. 满足标准,分割完毕
  4. 不满足标准,确认应该向哪方移动分割点。
    1. 若数组1左边最大的元素大于数组2右边最小的元素,则向左移动
    2. 若数组2左边最大的元素大于数组1右边最小的元素,则向右移动
  5. 计算中位数

Go 代码实现

在 LeetCode 表现如下:

执行用时 :12 ms, 在所有 golang 提交中击败了96.87%的用户

内存消耗 :5.5 MB, 在所有 golang 提交中击败了79.21%的用户

import "math"

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	// 确定两个数组长度
	l1, l2 := len(nums1), len(nums2)

	// 保证二分元素数量少的数组
	if l1 > l2 {
		return findMedianSortedArrays(nums2, nums1)
	}

	//初始化变量
	var (
		leftMax1, leftMax2 int // 左边最大值,两个数组都要表示,用 1,2 区分
		rightMin1, rightMin2 int // 右边最小值,两个数组都要表示,用 1,2 区分
		cut1, cut2 int // 分割位置
		begin = 0 // 二分当前窗口起始索引
		end  = 2 * l1 // 二维当前窗口的结束索引
	)

	// 迭代二分
	for begin <= end {
		// nums1 二分
		cut1 = (begin + end) / 2
		// 利用 cut1 确定 cut2 的值
		cut2 = l1 + l2 - cut1

		// 若  cut1 == 0 意味着 数组1 的的全部元素都大中位数,那么就将 leftMax1 设置一个最小值,用于统计
		// 反之 cut1 != 0 意味着 leftMax1 的值暂时定为 切割位置的元素值
		if cut1 == 0 {
			leftMax1 = math.MinInt64
		} else {
			leftMax1 = nums1[(cut1-1)/2]
		}
		// 若 cut1 == 2 * li 意味着 数组1 的全部元素都大于中位数,那么就另 rightMin1 设置为最大值,用于统计
		// 反之 rightMin1 暂定为切割位置元素
		if cut1 == 2 * l1 {
			rightMin1 = math.MaxInt64
		} else {
			rightMin1 = nums1[cut1/2]
		}
		// 数组2 中的切割位置同理
		if cut2 == 0 {
			leftMax2 = math.MinInt64
		} else {
			leftMax2 = nums2[(cut2-1)/2]
		}
		if cut2 == 2 * l2 {
			rightMin2 = math.MaxInt64
		} else {
			rightMin2 = nums2[cut2/2]
		}

		// 测试是否满足 数组1,2 的左边同时小于数组1,2 的右边,若不满足,移动二分窗口

		// 若数组1 的左边存在比数组2 的右边大的数,则切割位置应该在当前切割位置的左边,因此开始不变,结束位置为当前切割位置
		if leftMax1 > rightMin2 {
			end = cut1 -1
		} else  if leftMax2 > rightMin1 {
			begin = cut1 + 1
		} else {
			break
		}
	}

	// 找出切割位置左边最大值和右边最小值,求和/2 即可
	leftMax := leftMax1
	if leftMax1 < leftMax2 {
		leftMax = leftMax2
	}
	rightMin := rightMin1
	if rightMin1 > rightMin2 {
		rightMin = rightMin2
	}
	return float64(leftMax + rightMin) / 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76