[LintCode/LeetCode] Median of two Sorted Arrays

vvpvvp 发布于2019-08-14 15:41 / 1828人阅读

摘要：由于要求的时间，所以选择二分法。思路是找到两个数组合并起来的第个元素。这样只需计算两个数组的中位数是第几个元素，代入功能函数即可。据此，根据二分法的性质，我们在递归时可以将前即个元素排除。

Problem

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.

Example

Given A=[1,2,3,4,5,6] and B=[2,3,4,5], the median is 3.5.

Given A=[1,2,3] and B=[4,5], the median is 3.

Challenge

The overall run time complexity should be O(log (m+n)).

Note

由于要求O(log(m+n))的时间，所以选择二分法。
思路是找到两个数组合并起来的第k个元素。这样,只需计算两个数组的中位数是第几个元素，代入功能函数即可。当然，这里要先判断总长度的奇偶性，若为奇数，则取中间的元素；若为偶数，则计算中间两个数的平均值。

有两点需要注意：
在功能函数findKth()中，虽然是寻找第k个元素，但是对应数组的顺序是k-1，；
由于二分搜索需要不断递归，所以极限情况是k为1的时候，此时要返回A和B中首元素较小的那个。

二分搜索第k个元素的原理：
首先，找到k个元素的中点mid，令mid = k/2-1；
假设数组A和B的长度都大于首元素加上mid个元素的长度，那么，对于我们的数组A的前mid个元素和数组B的前mid个元素，一定不包含要找的第k个元素。
据此，根据二分法的性质，我们在递归时可以将前mid+1（即k/2）个元素排除。
那么，排除A还是B的前mid+1个元素呢？
比较一下A和B的第mid+1个元素，哪个小就排除该数组的前mid+1个元素。
然后，继续递归查找第k-k/2个元素。

Solution

    class Solution {
        public double findMedianSortedArrays(int[] A, int[] B) {
            int len = A.length + B.length;
            if (len % 2 == 0) return (findKth(A, 0, B, 0, len/2)+findKth(A, 0, B, 0, len/2+1))/2.0;
            else return findKth(A, 0, B, 0, len/2+1);
        }
        public double findKth(int[] A, int Astart, int[] B, int Bstart, int k) {
            if (Astart == A.length) return B[Bstart+k-1];
            else if (Bstart == B.length) return A[Astart+k-1];
            if (k == 1) return Math.min(A[Astart], B[Bstart]);
            int mid = k/2-1, kNew = k-k/2, kA = Integer.MAX_VALUE, kB = kA;
            if (Astart + mid < A.length) kA = A[Astart+mid];
            if (Bstart + mid < B.length) kB = B[Bstart+mid];
            if (kA < kB) return findKth(A, Astart+k/2, B, Bstart, kNew);
            else return findKth(A, Astart, B, Bstart+k/2, kNew);
        }
    }

Naive method: O(m+n) time

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length, n2 = nums2.length;
        int len = n1+n2;
        if (len%2 == 0) return (find(nums1, nums2, len/2)+find(nums1, nums2, len/2+1))/2.0;
        else return (double)find(nums1, nums2, len/2+1);
    }
    public int find(int[] A, int[] B, int k) {
        int res = 0;
        int i = 0, j = 0;
        while (k != 0 && i < A.length && j < B.length) {
            if (A[i] < B[j]) res = A[i++];
            else res = B[j++];
            k--;
        }
        if (k != 0) {
            if (i < A.length) res = A[i+k-1];
            else res = B[j+k-1];
        }
        return res;
    }
}

Update 2018.8

//没有使用二分法我觉得是一种退步
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int totalLength = nums1.length + nums2.length;
        int[] nums = new int[totalLength];
        int i = 0, j = 0, k = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] <= nums2[j]) {
                nums[k++] = nums1[i++];
            } else {
                nums[k++] = nums2[j++];
            }
        }
        while (i < nums1.length) {
            nums[k++] = nums1[i++];
        }
        while (j < nums2.length) {
            nums[k++] = nums2[j++];
        }
        if (totalLength % 2 == 0) {
            return (double) (nums[totalLength/2-1] + nums[totalLength/2])/2;
        } else {
            return (double) nums[totalLength/2];
        }
    }
}

云服务器 GPU云服务器 Median Arrays Sorted Arrays类

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

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

[LintCode/LeetCode] Find Median From / Data Stream

摘要：建立两个堆，一个堆就是本身，也就是一个最小堆另一个要写一个，使之成为一个最大堆。我们把遍历过的数组元素对半分到两个堆里，更大的数放在最小堆，较小的数放在最大堆。同时，确保最大堆的比最小堆大，才能从最大堆的顶端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...

zxhaaa 2019-08-14 14:35 评论0 收藏0
【leetcode长跑】开个头 Median of Two Sorted Arrays

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

荆兆峰 2019-08-21 17:24 评论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-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] Merge Sorted Array

Problem Given two sorted integer arrays A and B, merge B into A as one sorted array. Notice You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements ...

summerpxy 2019-08-14 15:41 评论0 收藏0