LeetCode 第 4 题：“寻找两个有序数组的中位数”题解

作者: 李威威 | 来源:发表于2019-07-24 23:38 被阅读0次

题解地址：二分查找短数组的“边界线”，长数组的“边界线”自动确定（Python 代码、Java 代码）。

说明：文本首发在力扣的题解版块，更新也会在第 1 时间在上面的网站中更新，这篇文章只是上面的文章的一个快照，您可以点击上面的链接看到其他网友对本文的评论。

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

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

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

示例 1:

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

则中位数是 2.0
示例 2:

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

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

二分查找短数组的“边界线”，长数组的“边界线”自动确定（Python 代码、Java 代码）

方法一：根据定义，合并、排序以后取中位数（时间复杂度不符合要求）

这应该是最简单直接的做法，即根据定义来做。考虑如下两种情况：

情况 1：如果合并以后的数组的长度是偶数，中位数有 2 个，此时取它们的平均值；
情况 2：如果合并以后的数组的长度是奇数；中位数有 1 个，把这个值返回即可。

说明：这个解法虽然不符合题目要求，但是是常规思路。并且它的优点也很显著：即在输入数组不是有序数组的时候，这个算法依然有效，因此如果这一题出现在面试中，向面试官提到这个最简单的思路，我觉得也是有必要的（一定要把它的这个优点连带说出来）。

参考代码 1：

Python 代码：

from typing import List


class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)
        nums1.extend(nums2)

        nums1.sort()

        if (m + n) & 1:
            return nums1[(m + n - 1) >> 1]
        else:
            return (nums1[(m + n - 1) >> 1] + nums1[(m + n) >> 1]) / 2

Java 代码：

import java.util.Arrays;

public class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int m = nums1.length;
        int n = nums2.length;

        int[] merge = new int[m + n];
        System.arraycopy(nums1, 0, merge, 0, m);
        System.arraycopy(nums2, 0, merge, m, n);

        Arrays.sort(merge);

        if (((m + n) & 1) == 1) {
            return merge[(m + n - 1) >>> 1];
        } else {
            return (double) (merge[(m + n - 1) >>> 1] + merge[(m + n) >>> 1]) / 2;
        }
    }

}

复杂度分析：

时间复杂度： $O((M + N) \log (M + N))$ ，这里 $M$ 是数组 nums1 的长度， $N$ 是数组 nums2 的长度。
空间复杂度： $O(M+ N)$ 。

分析：

优点：

1、简单、直接，编码出错的概率低；
2、在输入数组是非有序数组的时候，算法依然有效。

缺点：
1、空间复杂度高：这个算法连排序都做好了，得使用两个数组的长度之和的空间；
2、时间复杂度高：得看完所有的两个数组的数。

根据以上分析的两个缺点，在思路上我们有如下优化：我们可以不用拼在一起再排序，使用“归并排序的子过程”也可以得到一个更长的有序数组，从而得到这个更长的有序数组的中位数。

可以在「力扣」第 88 题：合并两个有序数组的题解《思路没有创新的地方，主要提供逻辑清楚的代码和编码细节（Python 代码、Java 代码）》中看到如何归并两个有序数组。不过我们没有必要搞一个新数组真的去合并，设置两个指针在数组上移动即可。仔细思考过后，还发现实际上没有必要“归并”完全，在归并的时候，我们只要看完排在前面的一半的数就可以了。

方法二：使用“归并排序”的子过程（时间复杂度不符合要求）

4-0.png

数组长度之和是奇数的时候，要看到索引为 $\cfrac{m - 1}{2}$ 的这个数，数组长度之和是偶数时，要看到索引为 $\cfrac{m}{2}$ 的这个数。

有两种思路：

思路1（不采用）：

不管长度之和是奇数还是偶数，直接先看到索引为 $\cfrac{m - 1}{2}$ 的这个数，如果是奇数，就可以返回了，如果是偶数，再往下看一个数；

编码的时候，发现，会有一些冗余的代码，并且要考虑一些边界的问题，例如看索引为 $\cfrac{m}{2}$ 的数的时候，可能 nums1 和 nums2 其中之一已经看完。

思路2（采用）：

那么不管奇数偶数，我都看到索引为 $\cfrac{m}{2}$ 的这个数，那么索引为 $\cfrac{m - 1}{2}$ 的这个数肯定看过了。

技巧：

1、我只关心最近看到的这两个数，那么我不妨将它们放置在一个长度为 $2$ 的数组中，使用计数器模 $2$ 的方式计算索引（这个技巧貌似叫做“滚动变量”），这样空间复杂度就可以降到常数。

2、在编码的时候，使用 counter 这个指针表示最后一次赋值的那个索引，初始化的时候，应该为 $-1$ ，在每一次循环开始之前 ++ 。

参考代码 2：

Python 代码：

from typing import List


class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)
        # 最后要找到合并以后索引是 median_index 的这个数
        median_index = (m + n) >> 1

        # nums1 的索引
        i = 0
        # nums2 的索引
        j = 0

        # 计数器从 -1 开始，在循环开始之前加 1
        # 这样在退出循环的时候，counter 能指向它最后赋值的那个元素
        counter = -1

        res = [0, 0]
        while counter < median_index:
            counter += 1
            # 先写 i 和 j 遍历完成的情况，否则会出现数组下标越界
            if i == m:
                res[counter & 1] = nums2[j]
                j += 1
            elif j == n:
                res[counter & 1] = nums1[i]
                i += 1
            elif nums1[i] < nums2[j]:
                res[counter & 1] = nums1[i]
                i += 1
            else:
                res[counter & 1] = nums2[j]
                j += 1
            # print(res)
            # 每一次比较，不论是 nums1 中元素出列，还是 nums2 中元素出列
            # 都会选定一个数，因此计数器 + 1

        # 如果 m + n 是奇数，median_index 就是我们要找的
        # 如果 m + n 是偶数，有一点麻烦，要考虑其中有一个用完的情况，其实也就是把上面循环的过程再进行一步

        if (m + n) & 1:
            return res[counter & 1]
        else:
            return sum(res) / 2

Java 代码：

public class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;

        // 最后要找到合并以后索引是 median_index 的这个数
        int medianIndex = (m + n) >>> 1;

        // 计数器从 -1 开始，在循环开始之前加 1
        // 这样在退出循环的时候，counter 能指向它最后赋值的那个元素
        int counter = -1;

        // nums1 的索引
        int i = 0;
        // nums2 的索引
        int j = 0;

        int[] res = new int[]{0, 0};
        while (counter < medianIndex) {
            counter++;
            // 先写 i 和 j 遍历完成的情况，否则会出现数组下标越界
            if (i == m) {
                res[counter & 1] = nums2[j];
                j++;
            } else if (j == n) {
                res[counter & 1] = nums1[i];
                i++;
            } else if (nums1[i] < nums2[j]) {
                res[counter & 1] = nums1[i];
                i++;
            } else {
                res[counter & 1] = nums2[j];
                j++;
            }
        }
        
        // 如果 m + n 是奇数，median_index 就是我们要找的
        // 如果 m + n 是偶数，有一点麻烦，要考虑其中有一个用完的情况，其实也就是把上面循环的过程再进行一步
        if (((m + n) & 1) == 1) {
            return res[counter & 1];
        } else {
            return (double) (res[0] + res[1]) / 2;
        }
    }
}

复杂度分析：

时间复杂度： $O(M + N)$ ，这里 $M$ 是数组 nums1 的长度， $N$ 是数组 nums2 的长度，看了数组长度之和的一半，常数系数视为 $1$ 。
空间复杂度： $O(1)$ ，这里候选值数组 res 只占 $2$ 个空间，用到的其它辅助变量也只有常数个。

接下来的这个思路是符合题目对时间复杂度要求的，但是我个人觉得偏难。它的优点当然在于时间复杂度低，能够很快胜任，但这个算法不一定好。

1、编码较困难，得考虑清楚不同的边界情况，因此编码出错的概率很高；

2、调试困难，出了什么问题，自己调试起来也未必很快就能找到原因，尤其是在一些边界条件的时候（这道题的边界条件在下面这个 PPT 的第 5 张，我画了 6 张图）；

3、相对于方法一：在输入数组如果不是有序数组的话，该算法失效。

因此，也不是非常好的算法，处处都“碾压”一个看起来比较不怎样的算法，简单、好想的算法也有它的用武之地，要针对具体的场景选择使用不同的方法。

下面这个方法是我看了很多朋友的题解，最终在 LeetCode 的英文版的官方题解一个评论里看到的思路和代码，思路我是用自己的话写了出来，希望能够对大家有所帮助。

思路很简单，找两个有序数组的分割。编码上有一点点技巧，特别是在处理边界条件的时候。

我个人觉得这样的问题看别人的题解的时候，先看个大概，懂得大致的思路，这相当于接受了他人的提示，然后尝试自己编码能不能做出来。然后还有一点是很重要的，很多算法题我都是得在纸上打个草稿，才能把思路和边界条件想清楚明白，所以一定不能偷懒。

方法三：使用二分法找两个数组的“边界线”

（温馨提示：下面的幻灯片建议您点击右下角的前进 “▶|” 或者后退 “|◀” 按钮以控制播放。）

4-1.png

4-2.png

4-3.png

4-4.png

4-5.png

4-6.png

4-7.png

4-8.png

4-9.png

4-10.png

参考代码 3：使用《“神奇的”二分查找法模板》写出的代码，使用这个模板会快一点点，但是用不好的话，比较容易采坑，如果不熟悉这个模板的朋友，可以直接跳到“参考代码 4”。

Python 代码：

from typing import List


class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # 为了让搜索范围更小，我们始终让 num1 是那个更短的数组，PPT 第 9 张
        if len(nums1) > len(nums2):
            # 这里使用了 pythonic 的写法，即只有在 Python，中可以这样写
            # 在一般的编程语言中，得使用一个额外变量，通过"循环赋值"的方式完成两个变量的地址的交换
            nums1, nums2 = nums2, nums1

        # 上述交换保证了 m <= n，在更短的区间 [0, m] 中搜索，会更快一些
        m = len(nums1)
        n = len(nums2)

        # 使用二分查找算法在数组 nums1 中搜索一个索引 i，PPT 第 9 张
        left = 0
        right = m

        # 因为 left_total 这个变量会一直用到，因此单独赋值，表示左边粉红色部分一共需要的元素个数
        left_total = (m + n + 1) >> 1
        while left < right:
            # 尝试要找的索引，在区间里完成二分，为了保证语义，这里就不定义成 mid 了
            # 用加号和右移是安全的做法，即使在溢出的时候都能保证结果正确，但是 Python 中不存在溢出
            # 参考：https://leetcode-cn.com/problems/guess-number-higher-or-lower/solution/shi-fen-hao-yong-de-er-fen-cha-zhao-fa-mo-ban-pyth/
            i = (left + right) >> 1
            j = left_total - i

            # 如果 nums1 左边最大值 > nums2 右边最小值
            if nums2[j - 1] > nums1[i]:
                # 这个分支缩短边界的原因在 PPT 第 8 张，情况 ①
                left = i + 1
            else:
                # 这个分支缩短边界的原因在 PPT 第 8 张，情况 ②
                # 【注意】：不让它收缩的原因是讨论 nums1[i - 1] > nums2[j]，i - 1 在数组的索引位置，在 i = 0 时越界
                right = i

        # 退出循环的时候，交叉小于等于一定关系成立，那么中位数就可以从"边界线"两边的数得到，原因在 PPT 第 2 张、第 3 张
        i = left
        j = left_total - left

        # 边界值的特殊取法的原因在 PPT 第 10 张
        nums1_left_max = float('-inf') if i == 0 else nums1[i - 1]
        nums1_right_min = float('inf') if i == m else nums1[i]

        nums2_left_max = float('-inf') if j == 0 else nums2[j - 1]
        nums2_right_min = float('inf') if j == n else nums2[j]

        # 已经找到解了，分数组之和是奇数还是偶数得到不同的结果，原因在 PPT 第 2 张
        if (m + n) & 1:
            return max(nums1_left_max, nums2_left_max)
        else:
            return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2

Java 代码：

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 为了让搜索范围更小，我们始终让 num1 是那个更短的数组，PPT 第 9 张
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        // 上述交换保证了 m <= n，在更短的区间 [0, m] 中搜索，会更快一些
        int m = nums1.length;
        int n = nums2.length;

        // 使用二分查找算法在数组 nums1 中搜索一个索引 i，PPT 第 9 张
        int left = 0;
        int right = m;
        // 这里使用的是最简单的、"传统"的二分查找法模板，使用"高级的"二分查找法模板在退出循环时候处理不方便
        while (left <= right) {
            // 尝试要找的索引，在区间里完成二分，为了保证语义，这里就不定义成 mid 了
            // 用加号和右移是安全的做法，即使在溢出的时候都能保证结果正确，但是 Python 中不存在溢出
            // 参考：https://leetcode-cn.com/problems/guess-number-higher-or-lower/solution/shi-fen-hao-yong-de-er-fen-cha-zhao-fa-mo-ban-pyth/
            int i = (left + right) >>> 1;
            // j 的取值在 PPT 第 7 张
            int j = ((m + n + 1) >>> 1) - i;

            // 边界值的特殊取法的原因在 PPT 第 10 张
            int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
            int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];

            int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
            int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

            // 交叉小于等于关系成立，那么中位数就可以从"边界线"两边的数得到，原因在 PPT 第 2 张、第 3 张
            if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {
                // 已经找到解了，分数组之和是奇数还是偶数得到不同的结果，原因在 PPT 第 2 张
                if (((m + n) & 1) == 1) {
                    return Math.max(nums1LeftMax, nums2LeftMax);
                } else {
                    return (double) ((Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))) / 2;
                }
            } else if (nums2LeftMax > nums1RightMin) {
                // 这个分支缩短边界的原因在 PPT 第 8 张
                left = i + 1;
            } else {
                // 这个分支缩短边界的原因在 PPT 第 8 张
                right = i - 1;
            }
        }
        throw new IllegalArgumentException("传入无效的参数，输入的数组不是有序数组，算法失效");
    }
}

参考代码 4：使用“传统的”二分查找法模板写出的代码。

Python 代码：

from typing import List


class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # 为了让搜索范围更小，我们始终让 num1 是那个更短的数组，PPT 第 9 张
        if len(nums1) > len(nums2):
            # 这里使用了 pythonic 的写法，即只有在 Python，中可以这样写
            # 在一般的编程语言中，得使用一个额外变量，通过"循环赋值"的方式完成两个变量的地址的交换
            nums1, nums2 = nums2, nums1

        # 上述交换保证了 m <= n，在更短的区间 [0, m] 中搜索，会更快一些
        m = len(nums1)
        n = len(nums2)

        # 使用二分查找算法在数组 nums1 中搜索一个索引 i，PPT 第 9 张
        left = 0
        right = m

        # 这里使用的是最简单的、"传统"的二分查找法模板
        while left <= right:
            # 尝试要找的索引，在区间里完成二分，为了保证语义，这里就不定义成 mid 了
            # 用加号和右移是安全的做法，即使在溢出的时候都能保证结果正确，但是 Python 中不存在溢出
            # 参考：https://leetcode-cn.com/problems/guess-number-higher-or-lower/solution/shi-fen-hao-yong-de-er-fen-cha-zhao-fa-mo-ban-pyth/
            i = (left + right) >> 1
            j = ((m + n + 1) >> 1) - i

            # 边界值的特殊取法的原因在 PPT 第 10 张
            nums1_left_max = float('-inf') if i == 0 else nums1[i - 1]
            nums1_right_min = float('inf') if i == m else nums1[i]

            nums2_left_max = float('-inf') if j == 0 else nums2[j - 1]
            nums2_right_min = float('inf') if j == n else nums2[j]

            # 交叉小于等于关系成立，那么中位数就可以从"边界线"两边的数得到，原因在 PPT 第 2 张、第 3 张
            if nums1_left_max <= nums2_right_min and nums2_left_max <= nums1_right_min:
                # 已经找到解了，分数组之和是奇数还是偶数得到不同的结果，原因在 PPT 第 2 张
                if (m + n) & 1:
                    return max(nums1_left_max, nums2_left_max)
                else:
                    return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2
            elif nums1_left_max > nums2_right_min:
                # 这个分支缩短边界的原因在 PPT 第 8 张，情况 ②
                right = i - 1
            else:
                # 这个分支缩短边界的原因在 PPT 第 8 张，情况 ①
                left = i + 1
        raise ValueError('传入无效的参数，输入的数组不是有序数组，算法失效')

Java 代码：

public class Solution4 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 为了让搜索范围更小，我们始终让 num1 是那个更短的数组，PPT 第 9 张
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        // 上述交换保证了 m <= n，在更短的区间 [0, m] 中搜索，会更快一些
        int m = nums1.length;
        int n = nums2.length;

        // 使用二分查找算法在数组 nums1 中搜索一个索引 i，PPT 第 9 张
        int left = 0;
        int right = m;

        // 因为 left_total 这个变量会一直用到，因此单独赋值，表示左边粉红色部分一共需要的元素个数
        int totalLeft = (m + n + 1) >>> 1;
        while (left < right) {
            // 尝试要找的索引，在区间里完成二分，为了保证语义，这里就不定义成 mid 了
            // 用加号和右移是安全的做法，即使在溢出的时候都能保证结果正确，但是 Python 中不存在溢出
            // 参考：https://leetcode-cn.com/problems/guess-number-higher-or-lower/solution/shi-fen-hao-yong-de-er-fen-cha-zhao-fa-mo-ban-pyth/
            int i = (left + right) >>> 1;
            // j 的取值在 PPT 第 7 张
            int j = totalLeft - i;

            if (nums2[j - 1] > nums1[i]) {
                // 这个分支缩短边界的原因在 PPT 第 8 张，情况 ①
                left = i + 1;
            } else {
                // 这个分支缩短边界的原因在 PPT 第 8 张，情况 ②
                // 【注意】：不让它收缩的原因是讨论 nums1[i - 1] > nums2[j]，i - 1 在数组的索引位置，在 i = 0 时越界
                right = i;
            }
        }

        // 退出循环的时候，交叉小于等于一定关系成立，那么中位数就可以从"边界线"两边的数得到，原因在 PPT 第 2 张、第 3 张

        int i = left;
        int j = totalLeft - left;
        // 边界值的特殊取法的原因在 PPT 第 10 张
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];

        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];

        // 交叉小于等于关系成立，那么中位数就可以从"边界线"两边的数得到，原因在 PPT 第 2 张、第 3 张
        // 已经找到解了，分数组之和是奇数还是偶数得到不同的结果，原因在 PPT 第 2 张
        if (((m + n) & 1) == 1) {
            return Math.max(nums1LeftMax, nums2LeftMax);
        } else {
            return (double) ((Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))) / 2;
        }
    }
}

复杂度分析：

时间复杂度： $O(\log(\min(M,N)))$ ，为了使得搜索更快，我们把更短的数组设置为 nums1 ，因为使用二分查找法，在它的长度的对数时间复杂度内完成搜索。
空间复杂度： $O(1)$ ，只使用了常数个的辅助变量。

LeetCode 第 4 题：“寻找两个有序数组的中位数”题解

二分查找短数组的“边界线”，长数组的“边界线”自动确定（Python 代码、Java 代码）

方法一：根据定义，合并、排序以后取中位数（时间复杂度不符合要求）

方法二：使用“归并排序”的子过程（时间复杂度不符合要求）

方法三：使用二分法找两个数组的“边界线”

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读