Leetcode-4 Median of Two Sorted Arrays

Shihira 发布于2019-08-16 13:50 / 858人阅读

摘要：解法解法应该是最常见的一种解法，就是将两个数组头尾相加合并起来，然后重新排序，例如输入两个数组，合并之后变为，然后求出中位数。如果两个数组长度和为偶数，那么中位数有两个，否则只有一个

题目

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

You may assume nums1 and nums2 cannot be both empty.

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

解析

给出两个已经排序好的数组，求出两个数组合起来的中位数。
题目意思很清晰，条件和结果都很简单，条件是两个已经排序好的数组，结果需要两个数组合起来之后取中位数。

解法1

解法1应该是最常见的一种解法，就是将两个数组头尾相加合并起来，然后重新排序，例如输入 [1,2] [3,4] 两个数组，合并之后变为[1,2,3,4]，然后求出中位数。
这种解法很简洁，但是在内存和性能方面的表现非常的差，因为两个已经排列好的数组头尾相加合并之后会变成一个无序的数组，同时占用内存增加了一倍。

解法2

效率更高点的解法应该是利用好两个数组已经排序好的这个特性，通过游标记录移动路径，并记录移动的次数，当移动的次数达到两个数组的中位数时，取得游标附近的值，求得中位数。

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int num1Size = nums1.length , num2Size = nums2.length;
        double result = 0.0;
        int size = num1Size + num2Size;
        int index = 0;
        int num1Index = 0 , num2Index = 0;
        int[] medianArray = new int[2];
        int currentValue = 0;
        while(index <= size/2){
            if(num1Index >= num1Size){
                currentValue = nums2[num2Index++];
            }else if(num2Index >= num2Size){
                currentValue = nums1[num1Index++];
            }
            else if(nums1[num1Index] > nums2[num2Index]){
                currentValue = nums2[num2Index++];
            }
            else{
                currentValue = nums1[num1Index++];
            }
            medianArray[0] = medianArray[1];
            medianArray[1] = currentValue;
            index++;
        }
        // 如果两个数组长度和为偶数，那么中位数有两个，否则只有一个
        if(size%2==0){
            result = (medianArray[0] + medianArray[1]) / 2.0;
        }else{
            result = medianArray[1];
        }
        return result;
    }

idc机房托管专线服务 Median Arrays Sorted Arrays类

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

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

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

wudengzan 2019-08-14 17:05 评论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] 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