Loading...
墨滴

MelodyJerry

2021/07/29  阅读:54  主题:自定义主题1

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

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

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

给定两个大小分别为 mn 的正序(从小到大)数组 nums1nums2。请你找出并返回这两个正序数组的 中位数

示例 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 两个位置的数,取两者平均值。

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

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

空间复杂度:

② 分割线+二分查找

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

  • 假设m = nums1.lengthn = nums2.length

    • 确保数组nums1长度一定是不大于nums2
      • 若大于,则交换即可:
      • 递归findMedianSortedArrays(nums2, nums1)
    • inums1中分割线,则取值为[0, m],表示分割线左侧元素下标为[0, i-1],分割线右侧元素下标为[i, m-1];设jnums2中分割线,则取值为[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  阅读:54  主题:自定义主题1

作者介绍

MelodyJerry