[Leetcode] Median of Two Sorted Arrays 有序数组中位数

wuaiqiu 发布于2019-08-14 12:17 / 3154人阅读

摘要：最新解法及思路有两个有序数组和，他们的大小各是和，请找出这两个数组所有数的中位数，总得时间复杂度不超过归并计数法复杂度时间空间思路如果对时间复杂度没有要求，这个方法是实现起来最简单的，我们只需要从下往上依次数个元素即可。

Median of Two Sorted Arrays 最新解法及思路：https://yanjia.li/zh/2018/11/...

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)).

有两个有序数组nums1和nums2，他们的大小各是m和n，请找出这两个数组所有数的中位数，总得时间复杂度不超过O(log(m+n))

归并计数法 Merge and Count 复杂度

时间O(n) 空间O(1)

思路

如果对时间复杂度没有要求，这个方法是实现起来最简单的，我们只需要从下往上依次数(n+m)/2个元素即可。由于两个数组都已经排序，我们可以使用两个指针指向数组“底部”，通过比较两个数组“底部”的元素大小来决定计哪一个元素，同时将其所在数组的指针“向上”移一位。为了方便处理总元素为偶数的情况，这里将找中位数变成找第k小的元素。

注意

计数的循环是用来找到第k-1个元素的，最后return的时候再判断第k个元素是哪一个

在每次计数的循环中要先判断两个数组指针是否超界，在最后return之前也要判断一次

代码

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int total = len1 + len2;
        if(total % 2==0){
            return (findKth(nums1,nums2,total/2)+findKth(nums1,nums2,total/2+1))/2.0;
        } else {
            return findKth(nums1,nums2,total/2+1);
        }
    }
    private int findKth(int[] nums1, int[] nums2, int k){
        int p = 0, q = 0;
        for(int i = 0; i < k - 1; i++){
            if(p>=nums1.length && q=nums2.length && pnums2[q]){
                q++;
            } else {
                p++;
            }
        }
        if(p>=nums1.length) {
            return nums2[q];
        } else if(q>=nums2.length) {
            return nums1[p];
        } else {
            return Math.min(nums1[p],nums2[q]);
        }
    }
}

分治法 Divide and Conquer 复杂度

时间O(log(m+n)) 空间O(1)

思路

题目要求O(log(m+n))的时间复杂度，一般来说都是分治法或者二分搜索。首先我们先分析下题目，假设两个有序序列共有n个元素（根据中位数的定义我们要分两种情况考虑），当n为奇数时，搜寻第(n/2+1)个元素，当n为偶数时，搜寻第(n/2+1)和第(n/2)个元素，然后取他们的均值。进一步的，我们可以把这题抽象为“搜索两个有序序列的第k个元素”。如果我们解决了这个k元素问题，那中位数不过是k的取值不同罢了。

那如何搜索两个有序序列中第k个元素呢，这里又有个技巧。假设序列都是从小到大排列，对于第一个序列中前p个元素和第二个序列中前q个元素，我们想要的最终结果是：p+q等于k-1,且一序列第p个元素和二序列第q个元素都小于总序列第k个元素。因为总序列中，必然有k-1个元素小于等于第k个元素。这样第p+1个元素或者第q+1个元素就是我们要找的第k个元素。

所以，我们可以通过二分法将问题规模缩小，假设p=k/2-1，则q=k-p-1，且p+q=k-1。如果第一个序列第p个元素小于第二个序列第q个元素，我们不确定二序列第q个元素是大了还是小了，但一序列的前p个元素肯定都小于目标，所以我们将第一个序列前p个元素全部抛弃，形成一个较短的新序列。然后，用新序列替代原先的第一个序列，再找其中的第k-p个元素（因为我们已经排除了p个元素，k需要更新为k-p），依次递归。同理，如果第一个序列第p个元素大于第二个序列第q个元素，我们则抛弃第二个序列的前q个元素。递归的终止条件有如下几种：

较短序列所有元素都被抛弃，则返回较长序列的第k个元素（在数组中下标是k-1）

一序列第p个元素等于二序列第q个元素，此时总序列第p+q=k-1个元素的后一个元素，也就是总序列的第k个元素

注意

每次递归不仅要更新数组起始位置（起始位置之前的元素被抛弃），也要更新k的大小（扣除被抛弃的元素）

代码

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int k = (m + n) / 2;
        if((m+n)%2==0){
            return (findKth(nums1,nums2,0,0,m,n,k)+findKth(nums1,nums2,0,0,m,n,k+1))/2;
        }   else {
            return findKth(nums1,nums2,0,0,m,n,k+1);
        }
        
    }
    
    private double findKth(int[] arr1, int[] arr2, int start1, int start2, int len1, int len2, int k){
        // 保证arr1是较短的数组
        if(len1>len2){
            return findKth(arr2,arr1,start2,start1,len2,len1,k);
        }
        if(len1==0){
            return arr2[start2 + k - 1];
        }
        if(k==1){
            return Math.min(arr1[start1],arr2[start2]);
        }
        int p1 = Math.min(k/2,len1) ;
        int p2 = k - p1;
        if(arr1[start1 + p1-1]arr2[start2 + p2-1]){
            return findKth(arr1,arr2,start1,start2 + p2,len1,len2-p2,k-p2);
        } else {
            return arr1[start1 + p1-1];
        }
    }
}

专线服务云服务器 Median Arrays Sorted LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64391.html

Leetcode-4 Median of Two Sorted Arrays

摘要：解法解法应该是最常见的一种解法，就是将两个数组头尾相加合并起来，然后重新排序，例如输入两个数组，合并之后变为，然后求出中位数。如果两个数组长度和为偶数，那么中位数有两个，否则只有一个题目 There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the tw...

Shihira 2019-08-16 13:50 评论0 收藏0
Leetcode[4] Median of two sorted arrays

摘要：复杂度思路因为要找中位数，又是在两个的数组里面。所以考虑用二分法。二分法经常适合的接下来考虑如何二分。然后对和进行比较，记为和。所以为了缩小搜索范围，我们可以扔掉这些数，在的剩下来的数中和的数组中接着找。说明中没有个数可以寻找。 Leetcode[4] Median of two sorted arrays There are two sorted arrays nums1 and n...

sarva 2019-08-15 13:51 评论0 收藏0
【leetcode长跑】开个头 Median of Two Sorted Arrays

摘要：自第一篇收集向的文章发布后，近年半没更新这个专栏了。今天是分类中第一个的，叫做。不过这样需要两个数组各扫一遍，然而我们的目的只是要取到中间值，似乎并不用完整的扫一遍。那么也就意味着，我们最终要记录的值可能是两个。大家好，我叫张小猪。自第一篇收集向的文章发布后，近 1 年半没更新这个专栏了。最近面试中发现将近 60% 的候选人对于 bubble sort 面露难色，于是心悸于自己也忘...

荆兆峰 2019-08-21 17:24 评论0 收藏0
[LintCode/LeetCode] Median of two Sorted Arrays

摘要：由于要求的时间，所以选择二分法。思路是找到两个数组合并起来的第个元素。这样只需计算两个数组的中位数是第几个元素，代入功能函数即可。据此，根据二分法的性质，我们在递归时可以将前即个元素排除。 Problem There are two sorted arrays A and B of size m and n respectively. Find the median of the tw...

vvpvvp 2019-08-14 15:41 评论0 收藏0
Leetcode 4 Median of Two Sorted Arrays 两排序数组的中位数

摘要：难度为这个题目描述很清晰给出两个排序好的数组求这两个数组的中位数在解这个题的过程中会碰到以下的问题先合起来重新排序是不可行的时间复杂度太高为先归并排序也是不可行的时间复杂度为用类似桶排的方法时间复杂度为不可行可能会碰到多种全部大于或全部小于 There are two sorted arrays nums1 and nums2 of size m and n respectively...

wudengzan 2019-08-14 17:05 评论0 收藏0