「力扣」第 4 题：寻找两个有序数组的中位数（困难）

二分查找 减治算法
专题 2：二分查找
发布日期:   2017-05-17

「力扣」第 4 题：寻找两个有序数组的中位数（困难）

来源：力扣（LeetCode）

给定两个大小为 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

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

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

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

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

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

参考代码 1：

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;
        }
    }

}

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

复杂度分析：

  • 时间复杂度：$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：

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;
        }
    }
}

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

复杂度分析：

  • 时间复杂度：$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”。

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("传入无效的参数，输入的数组不是有序数组，算法失效");
    }
}

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

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

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;
        }
    }
}

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('传入无效的参数，输入的数组不是有序数组，算法失效')

复杂度分析：

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

（本节完）

文章作者： liweiwei1419
文章链接： https://liweiwei1419.gitee.io/leetcode-algo/2017/05/17/leetcode-algo/0004-median-of-two-sorted-arrays/
版权声明： 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
二分查找 减治算法
赏
评论
 上一篇
「力扣」第 33 题：搜索旋转排序数组（中等） 「力扣」第 33 题：搜索旋转排序数组（中等）
「力扣」第 33 题：搜索旋转排序数组（中等） 链接 题解链接 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0, 1, 2, 4, 5, 6, 7] 可能变为 [4, 5, 6, 7, 0, 1, 2]
2017-05-18 专题 2：二分查找
二分查找 减治算法
下一篇 
「二分查找」专题二：在循环体内部排除元素 「二分查找」专题二：在循环体内部排除元素
「二分查找」专题二：在循环体内部排除元素从哪些元素一定不是目标元素考虑做对这一类问题的思路是「排除法」。在本题解最开始其实已经介绍了，我们的思路是做排除法：具体是根据看到的 mid 位置的元素，排除掉不可能存在目标元素的区间，进而确定下一轮
2017-05-16 专题 2：二分查找
数组
  目录