Adrian Wang's blog

一个完全由AI生成，但是内容高质量的Blog

LeetCode 4.寻找两个正序数组的中位数 - 深入理解二分思想

Posted on Edited on In , ,
Symbols count in article: 5.4k Reading time ≈ 5 mins.

题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数。

要求算法的时间复杂度为 O(log (m+n))。

示例：

1
2
3
4
5
6
7
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3]，中位数 2

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4]，中位数 (2 + 3) / 2 = 2.5

解题思路

这道题乍看之下，似乎可以通过合并两个数组后找出中位数来解决，但这样做的时间复杂度是 O(m+n)，而题目要求 O(log(m+n))。一看到对数级的时间复杂度，我们应该想到二分查找。

核心思想

本题的核心思想是将两个数组进行虚拟切分，使得：

  1. 左半部分的元素个数等于右半部分（或者多一个，当总数为奇数时）
  2. 左半部分的所有元素都小于或等于右半部分的所有元素

找到这样的切分后，中位数就可以轻松计算出来了。

假设有两个数组：

1
2
nums1: [a1, a2, a3, a4, a5]
nums2: [b1, b2, b3, b4, b5, b6, b7]

我们的目标是在这两个数组中找出一个切分位置，将所有元素分为数量相等（或左侧多一个）的两部分：

1
2
左半部分：[a1, a2, a3 | b1, b2, b3, b4]
右半部分：[a4, a5 | b5, b6, b7]

当左半部分的最大值小于或等于右半部分的最小值时，我们就找到了正确的切分位置。中位数可以根据总元素个数的奇偶性计算：

  • 元素总数为奇数：中位数 = 左半部分的最大值
  • 元素总数为偶数：中位数 = (左半部分的最大值 + 右半部分的最小值) / 2

实现的关键点解析

1. 切分点的含义

重要的是，mid表示的是元素间的切分位置，而不是具体的元素。例如：

对于数组 [1, 3, 5, 7, 9]：

  • mid=0 表示在1之前切分：[] | [1, 3, 5, 7, 9]
  • mid=3 表示在7之前切分：[1, 3, 5] | [7, 9]
  • mid=5 表示在所有元素之后切分：[1, 3, 5, 7, 9] | []

这就是为什么right初始化为len1而不是len1-1，因为我们需要考虑将所有元素都放在左半部分的情况。

2. 为什么使用 left <= right 而不是 left < right？

在这个二分查找中，使用 left <= right 是必要的。当搜索区间收缩到只有一个元素时（即 left == right），这个元素可能就是正确的切分点。如果使用 left < right，循环会提前退出，可能会错过正确解。

特别是当nums1只有一个元素时，如果使用 left < right，算法可能无法正确处理这种情况。

3. 为什么只检查 mid1 < len1 和 mid1 > 0，不检查 mid2 的边界？

这是一个很好的问题！算法中我们检查了：

1
2
3
4
5
if mid1 < len1 && nums1[mid1] < nums2[mid2-1] {
    // ...
} else if mid1 > 0 && nums1[mid1-1] > nums2[mid2] {
    // ...
}

不需要检查mid2的边界，原因如下：

  1. mid2的计算保证了某些边界条件：mid2 = halfLen - mid1，其中halfLen = (len1+len2+1)/2

  2. mid2的范围是有保证的：

    • 当mid1增大时，mid2减小，反之亦然
    • 我们知道 0 <= mid1 <= len1，因此 (halfLen-len1) <= mid2 <= halfLen

  3. 算法保证了mid2的合理性：

    • 我们总是对较短的数组进行二分（通过交换nums1和nums2确保len1 <= len2）
    • 这确保了halfLen-len1 >= 0，即mid2 >= 0
    • 同样，由于halfLen <= (len1+len2+1)/2 <= (len2+len2+1)/2，可以推导出mid2 <= len2

因此，对mid1进行边界检查已经足够，不需要显式检查mid2的边界。这是算法设计的巧妙之处。

4. 为什么halfLength计算要加1？

在代码中，我们看到halfLength的计算使用了：

1
halfLength := (len1+len2+1)>>1  // 左半部分应该包含的元素个数

这里的+1非常关键，它确保了在奇数长度的情况下，左半部分会多包含一个元素。让我们分析不同情况：

情况1：总长度为偶数
假设len1 + len2 = 8

  • 使用(8) >> 1 = 4，左边和右边各4个元素
  • 使用(8 + 1) >> 1 = 4，结果相同，左右各4个元素

情况2：总长度为奇数
假设len1 + len2 = 7

  • 使用(7) >> 1 = 3，左边3个元素，右边4个元素
  • 使用(7 + 1) >> 1 = 4，左边4个元素，右边3个元素

在处理中位数时，我们的代码逻辑是：

1
2
3
4
5
6
7
// 如果两个数组的总长度为奇数，中位数就是左半部分的最大值
if (len1+len2)%2 == 1 {
    return float64(maxLeft)
}

// 总长度为偶数时，中位数是左半部分最大值和右半部分最小值的平均值
return float64(maxLeft + minRight) / 2.0

这里的算法设计假设：

  • 奇数长度时，中位数是左半部分的最大值
  • 偶数长度时，需要计算左半部分最大值和右半部分最小值的平均值

为了使这个逻辑正确工作，在奇数长度情况下，我们必须确保中位数在左半部分。例如，对于总长度7的数组，中位数是第4个元素，所以左半部分必须包含4个元素。

这就是为什么要使用(len1+len2+1)>>1而不是(len1+len2)>>1的原因：加上这个+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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/**
 * 寻找两个正序数组的中位数
 * @param nums1 第一个有序数组
 * @param nums2 第二个有序数组
 * @return 两个数组合并后的中位数
 */
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    // 获取两个数组的长度
    len1, len2 := len(nums1), len(nums2)
    
    // 优化：始终对较短的数组进行二分查找，减少搜索空间
    // 如果 nums1 比 nums2 长，则交换两个数组
    if len1 > len2 {
        return findMedianSortedArrays(nums2, nums1)
    }
    
    // 二分查找的边界
    left := 0                   // 二分查找的左边界，表示nums1可能的最小切分点
    right := len1               // 二分查找的右边界，表示nums1可能的最大切分点
    halfLen := (len1+len2+1)/2  // 左半部分应该包含的元素个数（包括奇数情况）
    
    // 在nums1上进行二分查找，寻找合适的切分点
    for left <= right {
        // 计算当前nums1的切分点（将前mid1个元素放入左半部分）
        mid1 := (left + right) >> 1  // 使用位运算提高效率，等价于 (left + right) / 2
        
        // 根据mid1计算nums2的切分点，确保左半部分总共有halfLen个元素
        mid2 := halfLen - mid1
        
        // 第一种情况：nums1的切分点太小，左半部分需要更多元素
        // 检查：如果mid1元素小于nums2的mid2-1元素，说明mid1需要右移
        if mid1 < len1 && nums1[mid1] < nums2[mid2-1] {
            // mid1太小，需要增加，向右移动left指针
            left = mid1 + 1
        } 
        // 第二种情况：nums1的切分点太大，左半部分需要减少元素
        // 检查：如果mid1-1元素大于nums2的mid2元素，说明mid1需要左移
        else if mid1 > 0 && nums1[mid1-1] > nums2[mid2] {
            // mid1太大，需要减少，向左移动right指针
            right = mid1 - 1
        } 
        // 找到了合适的切分点：左半部分的最大值小于等于右半部分的最小值
        else {
            // 计算左半部分的最大值
            var maxLeft int
            
            // 处理边界情况：当mid1=0时，nums1的左半部分为空
            if mid1 == 0 {
                maxLeft = nums2[mid2-1]  // 左半部分最大值来自nums2
            } 
            // 处理边界情况：当mid2=0时，nums2的左半部分为空
            else if mid2 == 0 {
                maxLeft = nums1[mid1-1]  // 左半部分最大值来自nums1
            } 
            // 一般情况：取nums1和nums2左半部分的最大值
            else {
                maxLeft = max(nums1[mid1-1], nums2[mid2-1])
            }
            
            // 如果两个数组的总长度为奇数，直接返回左半部分的最大值
            if (len1+len2) % 2 == 1 {
                return float64(maxLeft)
            }
            
            // 计算右半部分的最小值（偶数情况下需要）
            var minRight int
            
            // 处理边界情况：当mid1=len1时，nums1的右半部分为空
            if mid1 == len1 {
                minRight = nums2[mid2]  // 右半部分最小值来自nums2
            } 
            // 处理边界情况：当mid2=len2时，nums2的右半部分为空
            else if mid2 == len2 {
                minRight = nums1[mid1]  // 右半部分最小值来自nums1
            } 
            // 一般情况：取nums1和nums2右半部分的最小值
            else {
                minRight = min(nums1[mid1], nums2[mid2])
            }
            
            // 总长度为偶数时，中位数是左半部分最大值和右半部分最小值的平均值
            return float64(maxLeft + minRight) / 2.0
        }
    }
    
    // 理论上不会执行到这里，添加返回值以满足编译要求
    return 0.0
}

/**
 * 返回两个整数中的较大值
 */
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

/**
 * 返回两个整数中的较小值
 */
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

实例分析

让我们通过一个具体例子来说明算法的执行过程：

假设 nums1 = [1, 3, 5]，nums2 = [2, 4, 6]

  1. 初始化：len1=3, len2=3, halfLen=(3+3+1)/2=3, left=0, right=3

  2. 第一次迭代：

    • mid1 = (0+3)/2 = 1，表示在nums1中[1] | [3,5]切分
    • mid2 = 3-1 = 2，表示在nums2中[2,4] | [6]切分
    • 检查：nums1[mid1-1]=1 <= nums2[mid2]=6 且 nums2[mid2-1]=4 > nums1[mid1]=3
    • 需要增加mid1，所以left = mid1+1 = 2

  3. 第二次迭代：

    • mid1 = (2+3)/2 = 2，表示在nums1中[1,3] | [5]切分
    • mid2 = 3-2 = 1，表示在nums2中[2] | [4,6]切分
    • 检查：nums1[mid1-1]=3 <= nums2[mid2]=4 且 nums2[mid2-1]=2 <= nums1[mid1]=5
    • 找到了合适的切分点！
    • 左半部分：[1, 3, 2]，最大值是3
    • 右半部分：[5, 4, 6]，最小值是4
    • 总元素个数为偶数，所以中位数 = (3+4)/2 = 3.5

复杂度分析

  • 时间复杂度：O(log(min(m,n)))，其中m和n分别是两个数组的长度。我们对较短的数组进行二分查找。
  • 空间复杂度：O(1)，只使用了常数额外空间。

总结

这道题的核心在于理解如何在两个有序数组中找到合适的切分点，使得：

  1. 左半部分和右半部分的元素个数大致相等
  2. 左半部分的所有元素小于等于右半部分的所有元素

关键点解析：

  • mid表示元素间的切分位置，而不是元素本身
  • 使用left <= right确保能检查所有可能的切分点
  • right初始化为len1以考虑所有可能的切分情况
  • 只需检查mid1的边界条件，因为算法设计已经保证了mid2的合理性

理解了这些关键点，这道Hard难度的题目就变得清晰易懂了。二分查找的应用远不止是在单一有序数组中查找元素，它还可以用来解决更复杂的问题，比如此题中的两个有序数组的中位数查找。