Leetcode-4 Median of Two Sorted Arrays

Shihira 發布于2019-08-16 13:50 / 982人閱讀

摘要：解法解法應該是最常見的一種解法，就是將兩個數組頭尾相加合并起來，然后重新排序，例如輸入兩個數組，合并之后變為，然后求出中位數。如果兩個數組長度和為偶數，那么中位數有兩個，否則只有一個

題目

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

云服務器 GPU云服務器 Median Arrays Sorted Arrays類

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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