国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Leetcode] Median of Two Sorted Arrays 有序數組中位數

wuaiqiu / 3304人閱讀

摘要：最新解法及思路有兩個有序數組和，他們的大小各是和，請找出這兩個數組所有數的中位數，總得時間復雜度不超過歸并計數法復雜度時間空間思路如果對時間復雜度沒有要求，這個方法是實現起來最簡單的，我們只需要從下往上依次數個元素即可。

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

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

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

  • 【leetcode長跑】開個頭 Median of Two Sorted Arrays

    摘要：自第一篇收集向的文章發布后，近年半沒更新這個專欄了。今天是分類中第一個的，叫做。不過這樣需要兩個數組各掃一遍，然而我們的目的只是要取到中間值，似乎并不用完整的掃一遍。那么也就意味著，我們最終要記錄的值可能是兩個。 大家好，我叫張小豬。 自第一篇收集向的文章發布后，近 1 年半沒更新這個專欄了。最近面試中發現將近 60% 的候選人對于 bubble sort 面露難色，于是心悸于自己也忘...

    荊兆峰 評論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 評論0 收藏0

  • Leetcode 4 Median of Two Sorted Arrays 兩排序數組的中位數

    摘要：難度為這個題目描述很清晰給出兩個排序好的數組求這兩個數組的中位數在解這個題的過程中會碰到以下的問題先合起來重新排序是不可行的時間復雜度太高為先歸并排序也是不可行的時間復雜度為用類似桶排的方法時間復雜度為不可行可能會碰到多種全部大于或全部小于 There are two sorted arrays nums1 and nums2 of size m and n respectively...

    wudengzan 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<