Loading...
墨滴

MelodyJerry

2021/07/29  阅读：61  主题：自定义主题1

4. 找两个正序数组的中位数

4. 找两个正序数组的中位数

难度 困难 通过率 40.49%
(458209/1131417)

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

示例 1：

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

示例 2：

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

示例 3：

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例 4：

输入：nums1 = [], nums2 = [1]
输出：1.00000

示例 5：

输入：nums1 = [2], nums2 = []
输出：2.00000

提示：

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m +n <= 2000
  • <= nums1[i], nums2[i] <=

进阶：

你能设计一个时间复杂度为 的算法解决此问题吗？

✔题解

① 归并查找

如果忽略进阶中的时间复杂度要求为 的话，是很快速、容易地解决地。

一个比较直观的做法：将两个数组合并，排序，然后分别取得 total / 2 和 (total - 1) / 2 两个位置的数，取两者平均值。

这样做的目的是为了避免分情况讨论：合并后的数组长度是奇数还是偶数。

时间复杂度：合并两个数组的复杂度是 ，对合并数组进行排序的复杂度是 。整体复杂度是 。

空间复杂度： 。

② 分割线+二分查找

使用二分法直接在两个数组中找中位数分割线，使得nums1和nums2中分割线满足以下性质即可根据分割线左右的数来确定中位数：

  • 假设m = nums1.length，n = nums2.length

    • 确保数组nums1的长度一定是不大于nums2的
      • 若大于，则交换即可:
      • 递归findMedianSortedArrays(nums2, nums1)
    • 设i为nums1中分割线，则取值为[0, m]，表示分割线左侧元素下标为[0, i-1]，分割线右侧元素下标为[i, m-1]；设j为nums2中分割线，则取值为[0, n]，表示分割线左侧元素下标为[0, j-1]，分割线右侧元素下标为[i, n-1]。

  • 为确保分割线左边个数要比右边个数多1，需要进行一个细节处理，m+n会有两种情况：

    • 正常下：
      • m+n为偶数：i + j = (m + n)/2 (5+5)/2=5
      • m+n为奇数：i + j = (m + n)/2（除以2是向下取整） (4+5)/2=4
    • 统一后：
      • m+n为偶数：i + j = (m + n + 1)/2 (5+5+1)/2=5
      • m+n为奇数：i + j = (m + n + 1)/2（现变为向上取整） (4+5+1)/2=5

  • 分割线左侧元素小于等于分割线右侧元素。由于两个数组均为正序数组，则只需要要求：nums1[i-1] <= nums2[j] && nums2[j-1] <= nums1[i]

  • 由于上该条件等价于在[0, m]中找到最大的i使得nums1[i-1] <= nums2[j]，因此可以使用二分查找。

    • 因为i+j=(m+n+1)/2，所以只要确定i，就能确定j了
      • j=(m+n+1)/2-i
    • 证明：假设我们已经找到了满足条件的最大i，使得nums1[i-1] <= nums2[j]，那么此时必有nums[i] > nums2[j]，进而有nums[i] > nums2[j-1]

  • 分割线找到后，若m+n为奇数，分割线左侧的最大值即为中位数；若为偶数，分割线左侧的最大值与分割线右侧的最小值的平均数即为中位数。

  • 时间复杂度：O(log(m, n))，空间复杂度：O(1)。

上述只是简单的描述，详细需要移步到下面的两种题解，我也是参考他们的题解来解决的，配合下面的视频。

推荐第1个题解，我的思路和他差不多，最关键是人家录了视频哈哈！

分割+二分+分治

视频题解：LeetCode004-两个有序数组的中位数-最优算法代码讲解[1]

作者：up主 甩手掌柜凡三岁[2]

分割线+二分查找

视频题解：4. 寻找两个正序数组的中位数[3]

文字题解：二分查找定位短数组的「分割线」（Java ）[4]

作者：李威威同学[5]

③ 从两个有序数组中找第 k 小的数

无意间发现三叶姐的题解，和其他题解有些不一样

来源：宫水三叶的思辨日记

首先可以将原问题等效为：从两个有序数组中找第 k 小的数。

分两种情况讨论：

  1. 总个数为偶数：找到 第 (total / 2) 个小的数 和 第 (total / 2 + 1) 个小的数，结果为两者的平均值。
  2. 总个数为奇数：结果为 第 (total / 2 + 1) 个小的数 。

具体思路为：

  • 默认第一个数组比第二个数组的有效长度短，如果不满足，则调换两个数组（这也是一个常用技巧，目的是减少边界处理工作：原本需要对两个数组做越界检查，现在只需要对短的数组做越界检查）
  • 第一个数组的有效长度从 i 开始，第二个数组的有效长度从 j 开始，其中 [i,si - 1] 是第一个数组的前 k / 2 个元素，[j,sj - 1] 是第二个数组的前 k - k / 2 个元素（为了确保 k 为奇数的时候正确）
  • 当 nums1[si - 1] > nums2[sj - 1]：则表示第 k 小一定不在 [j,sj - 1] 中，即在 [i,n] 或 [sj,m] 中
  • 当 nums1[si - 1] <= nums2[sj - 1]：则表示第 k 小一定不在 [i,si - 1] 中，即在 [si,n] 或 [j,m] 中 
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int tot = nums1.length + nums2.length;
        if (tot % 2 == 0) {
            int left = find(nums1, 0, nums2, 0, tot / 2);
            int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;
        } else {
            return find(nums1, 0, nums2, 0, tot / 2 + 1);
        }
    }
    int find(int[] n1, int i, int[] n2, int j, int k) {
        if (n1.length - i > n2.length - j) return find(n2, j, n1, i, k);
        if (i >= n1.length) return n2[j + k - 1];
        if (k == 1) {
            return Math.min(n1[i], n2[j]);
        } else {
            int si = Math.min(i + (k / 2), n1.length), sj = j + k - (k / 2);
            if (n1[si - 1] > n2[sj - 1]) {
                return find(n1, i, n2, sj, k - (sj - j));
            } else {
                return find(n1, si, n2, j, k - (si - i));
            }
        }
    }
}

时间复杂度：每次递归 k 的规模都减少一半，复杂度为

空间复杂度：

参考资料

[1]

LeetCode004-两个有序数组的中位数-最优算法代码讲解: https://www.bilibili.com/video/BV1H5411c7oC?from=search&seid=5223709810640990198

 [2]

甩手掌柜凡三岁: https://www.bilibili.com/video/BV1H5411c7oC?from=search&seid=5223709810640990198

 [3]

4. 寻找两个正序数组的中位数: https://www.bilibili.com/video/BV1Xv411z76J

 [4]

二分查找定位短数组的「分割线」（Java ）: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/he-bing-yi-hou-zhao-gui-bing-guo-cheng-zhong-zhao-/

 [5]

李威威: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/he-bing-yi-hou-zhao-gui-bing-guo-cheng-zhong-zhao-/

MelodyJerry

2021/07/29  阅读：61  主题：自定义主题1

作者介绍

MelodyJerry