Leetcode[4] Median of two sorted arrays

sarva 发布于2019-08-15 13:51 / 2634人阅读

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

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

Binary search

复杂度
O(lg(m + n))

思路
因为要找中位数，又是在两个sorted的数组里面。所以考虑用二分法。（二分法经常适合sorted的array).
接下来考虑如何二分。
假设第k个数是我们要找的中位数，那么前k-1个数应该都比这个第k个数要小。后面的数都比这个第k个数大。（像变形的用二分法找第K个数）。
如果我们每次在a数组中找前(k/2) = m个数，在b数组中找剩下的(k-k/2) = n个数。然后对a[p + k/2 - 1]和b[q + k - k/2 -1]进行比较，记为a[i]和b[j]。

a[i] < b[j]：说明我们可以扔掉0-i之间的（i+ 1）个数。为什么？
因为a数组中的前m个数的最大值都比b数组中的前n个数要小，那么这前m个数一定是在我们想要的中位数之前的，并且对找到中位数没有说明影响。所以为了缩小搜索范围，我们可以扔掉这些数，在a的剩下来的数中和b的数组中接着找。

i>=a.length: 说明a中没有m个数可以寻找。那么第K个数要么在b剩下的数组[n ~ b.length]中，要么就在a的前m个数中。

一直搜索到什么时候为止呢？
k=1代表的是，当前的这个是就是我们想要的值，我们应该在如何选择? Math.min(a[p], b[q]).

if(a[i] < b[j]) {
  search（a[right], b[0], k - m);
} else {
  search (a[0], b[right], k - n);
}

我们从找第K个数开始，一直到K=1，每次扔掉一部分数 k /2，所以时间复杂度是log(k).
K=(M + N) / 2, 所以时间复杂度是log(m + n)

代码

class Solution {
    // 其实找的是第k个值。
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        if(len % 2 == 0) {
            return findKthNumberInTwoArray(nums1, nums2, 0, 0, len / 2) / 2 
                + findKthNumberInTwoArray(nums1, nums2, 0, 0, len / 2 + 1) / 2;
        } else {
            return findKthNumberInTwoArray(nums1, nums2, 0, 0, len / 2 + 1);
        }     
    }
    
    // p is the start index of nums1, q is the start index of nums2, we wanna find the kth number 
    // in both num1 & nums2
    public double findKthNumberInTwoArray(int[] nums1, int[] nums2, int p, int q, int k) {
        if(p >= nums1.length) return nums2[q + k - 1];
        if(q >= nums2.length) return nums1[p + k - 1];
        if(k == 1) return Math.min(nums1[p], nums2[q]);
        
        int m = k / 2, n = k - m;
        // 因为当a数组没有中这个数的时候，说明第k一定在b数组剩余的数中和a数组的剩余数组中的一个。
        int aVal = Integer.MAX_VALUE, bVal = Integer.MAX_VALUE;
        if(p + m - 1 < nums1.length) aVal = nums1[p + m - 1];
        if(q + n - 1 < nums2.length) bVal = nums2[q + n - 1];
        
        if(aVal < bVal) {
            return findKthNumberInTwoArray(nums1, nums2, p + m, q, k - m);
        } else {
            return findKthNumberInTwoArray(nums1, nums2, p, q + n, k - n);
        }
    }
}

云服务器 GPU云服务器 sorted-array Median LeetCode two

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

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

【leetcode长跑】开个头 Median of Two Sorted Arrays

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

荆兆峰 2019-08-21 17:24 评论0 收藏0
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
[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
[Leetcode] Median of Two Sorted Arrays 有序数组中位数

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

wuaiqiu 2019-08-14 12:17 评论0 收藏0