当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.004.Median of Two Sorted Arrays 两个有序数组的中位数

LeetCode.004.Median of Two Sorted Arrays 两个有序数组的中位数

题目描述

004 Median of Two Sorted Arrays
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log(m+n)).

Example 1:*

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

The median is 2.0

Example 2:

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

The median is (2 + 3)/2 = 2.5

解题过程

O(m+n)归并排序法

我只会简单的归并排序法,写了一版,通过了,速度还不慢,打败了93%:
时间复杂度 O(m+n),空间复杂度 O(m+n)

// 归并排序法
private static class SolutionV2018 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length + nums2.length];
        int i = 0, j = 0, k = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] <= nums2[j]) {
                res[k++] = nums1[i++];
            } else {
                res[k++] = nums2[j++];
            }
        }
        while (i < nums1.length) {
            res[k++] = nums1[i++];
        }
        while (j < nums2.length) {
            res[k++] = nums2[j++];
        }
        return res.length % 2 == 0 ? (double) (res[res.length / 2] + res[(res.length / 2) - 1]) / 2 : res[res.length / 2];
    }
}

O(m+n)双指针计数第(m+n)/2个元素

还是归并的思想,但不需要真正做归并,中位数一定是两个数组的从前往后数第 (m+n)/2+1 个元素
若 m+n 是奇数,中位数是单个数,即第 (m+n)/2 + 1 个元素
若 m+n 是偶数,中位数是两个数,即第 (m+n)/2 和 第 (m+n)/2 + 1 个元素
用两个指针 i,j 分别从前往后遍历 nums1 和 nums2,哪个指针的元素值小就往后移动,并计数,遍历过程中用 preMediam 记录前一个元素,用于记录当 m+n 是偶数时的第一个中位数。
当数到第 (m+n)/2 + 1 个元素时,停止,根据 (m+n) 的奇偶性决定是返回 median 还是 (preMedian + median) / 2

相比于归并排序法,空间复杂度降为 O(1)
时间复杂度 O(m+n),空间复杂度 O(1)

// 中位数一定是两个数组的从前往后数第 (m+n)/2 个元素
private static class SolutionV202005Count {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 若 m+n 是奇数,中位数是单个数,即第 (m+n)/2 + 1 个元素
        // 若 m+n 是偶数,中位数是两个数,即第 (m+n)/2 和 第 (m+n)/2 + 1 个元素
        int medianCount = (nums1.length + nums2.length)/2 +1;
        // preMedian 是第 (m+n)/2 个元素,即当 m+n 是偶数时的第一个中位数
        int preMedian = 0, median = 0;
        int i = 0, j = 0;
        int count = 0; // 遍历的元素个数
        while (i < nums1.length || j < nums2.length) {
            if (i < nums1.length && j < nums2.length) {
                median = (nums1[i] < nums2[j]) ? nums1[i++] : nums2[j++];
            } else {
                median = (i == nums1.length) ? nums2[j++] : nums1[i++];
            }
            count++;
            if (count == medianCount) {
                break;
            }
            preMedian = median;
        }
        return (nums1.length + nums2.length) % 2 == 1 ? median : (double)(preMedian + median) / 2;
    }
}

O(log(m+n))二分搜索找第k小元素

要是面试的话,这时候肯定要问怎么优化了,看到复杂度要求为 O(log(m+n)),能想到肯定用二分、二叉来解决。
这道题转化为 求两个有序数组的第 k 小元素 问题,其中 k = (m+n)/2+1,可以通过二分搜索解决,当然如果 m+n 是偶数时需要求第 k-1 小和第 k 小的数。

这里的二分比较难理解,和普通的二分搜索不一样,普通二分搜索是对数组长度二分,这里是对 k 值二分。
我们要求第 k 小的元素,找每个数组的从前往后第 k/2 个元素,分别为 nums1[k/2]nums2[k/2],如果 nums1[k/2] <= nums2[k/2]nums1[0...k/2] 肯定不可能是第 k 小元素,将 nums1[k/2] 及其前面的元素排除,这里排除了 k/2 个元素,则继续从剩余子数组中寻找第 k-k/2 小的元素

为什么 如果 nums1[k/2] <= nums2[k/2]nums1[0...k/2] 肯定不可能是第 k 小元素
nums1[k/2] 前面有 0… k/2-1 共 k/2-1 个元素, nums2[k/2] 前面也有 k/2-1 个元素
如果 nums1[k/2] <= nums2[k/2] ,则 nums1[0…k/2-1] 肯定比 nums1[k/2] 小,nums2[0…k/2-1] 是否比 nums1[k/2] 小我们不知道,但我们可以假设也都比 nums1[k/2] 小,所以比 nums1[k/2] 小的元素个数最多是 (k/2-1)*2 = k-2 个,也就是说 nums1[k/2] 最大也只可能是从前往后数的第 k-1 小元素,他肯定不可能是第 k 小元素,所以可以排除 nums1[k/2] 以及 nums1 中在他之前的元素。

举个具体的例子

nums1 = 1, 20, 30, 40, 50
nums2 = 2, 22, 32, 42, 52, 62

一共 11 个元素,中位数就是第 11/2+1=6 小的元素,比较两个数组中第 6/2=3 个元素,也就是 30 和 32,有 30 小于 32,也就是 nums1[k/2] <= nums2[k/2],这里的例子就是 nums1[k/2] 最大的情况,也就是比 nums1[k/2] 小的元素个数最多的情况,可以看到 1, 20, 2, 22 都比 30 小,但即使在这种情况下 30 也只能是第 5 小元素,也就是第 k-1 小元素,不可能是第 k 小(也就是第 6 小)元素。

可以用递归实现找两个有序数组的第k小元素,但具体写起来还是有些难度的,可能要 debug 多调试几次,因为有好多边界情况,比如:
1、nums1 和 nums2 中第 k/2 个元素可能越界,此时只需用越界数组的最后一个元素代替做比较即可。
2、搜索过程中,其中一个数组可能搜索完毕了,也就是所有元素都被排除了,此时直接返回剩余数组中第 k 个元素即可,递归结束。
3、k = 1 时递归结束,直接比较两个子数组首元素返回较小者即可。

时间复杂度 O(logk) 由于 k = (m+n) / 2,所以时间复杂度也就是 O(log(m+n))
空间复杂度 O(1)

// 转化为求两个有序数组的第k小元素,二分搜索法解决
public static class SolutionV202005BinarySearch {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 两个有序数组的中位数即第 k 小的数(m+n 是偶数时需要求第 k-1 小和第 k 小的数)
        int k = (nums1.length + nums2.length) / 2 + 1;
        if ((nums1.length + nums2.length) % 2 == 1) {
            return getKthLeastElement(nums1, nums2, 0, 0, k);
        } else {
            int preKthLeast = getKthLeastElement(nums1, nums2, 0, 0, k - 1); // 第 k-1 小的元素
            int kthLeast = getKthLeastElement(nums1, nums2, 0, 0, k); // 第 k 小的元素
            return (preKthLeast + kthLeast) / 2.0;
        }
    }

    // 返回升序数组 nums1[nums1Start:] 和 nums2[nums2Start:] 中第 k 小的元素
    public int getKthLeastElement(int [] nums1, int [] nums2, int nums1Start, int nums2Start, int k) {
        // nums1 和 nums2 其中之一已结束,直接返回另一个数组的第 k 个元素
        if (nums1Start >= nums1.length || nums2Start >= nums2.length) {
            return nums1Start >= nums1.length ? nums2[nums2Start + k - 1] : nums1[nums1Start + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[nums1Start], nums2[nums2Start]);
        }
        int mid = k / 2;
        int nums1Value = nums1Start + mid - 1 < nums1.length ? nums1[nums1Start + mid - 1] : nums1[nums1.length - 1];
        int nums2Value = nums2Start + mid - 1 < nums2.length ? nums2[nums2Start + mid - 1] : nums2[nums2.length - 1];
        if (nums1Value <= nums2Value) {
            // 排除的元素个数
            int excludeCount = nums1Start + mid - 1 < nums1.length ? mid : nums1.length - nums1Start;
            // 从剩余子数组中找第 k - excludeCount 小的元素
            return getKthLeastElement(nums1, nums2, nums1Start + mid, nums2Start, k - excludeCount);
        } else {
            // 排除的元素个数
            int excludeCount = nums2Start + mid - 1 < nums2.length ? mid : nums2.length - nums2Start;
            // 从剩余子数组中找第 k - excludeCount 小的元素
            return getKthLeastElement(nums1, nums2, nums1Start, nums2Start + mid, k - excludeCount);
        }
    }
}

GitHub代码

algorithms/leetcode/leetcode/_004_MedianOfTwoSortedArrays.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_004_MedianOfTwoSortedArrays.java


上一篇 LeetCode.014.Longest Common Prefix 最长公共前缀

下一篇 LeetCode.009.Palindrome Number 判断整数是否回文数

阅读
评论
1,891
阅读预计9分钟
创建日期 2018-02-07
修改日期 2020-05-24
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论