亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

[Leetcode] Median of Two Sorted Arrays 有序數(shù)組中位數(shù)

wuaiqiu / 3357人閱讀

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

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)).
有兩個(gè)有序數(shù)組nums1和nums2，他們的大小各是m和n，請找出這兩個(gè)數(shù)組所有數(shù)的中位數(shù)，總得時(shí)間復(fù)雜度不超過O(log(m+n))
歸并計(jì)數(shù)法 Merge and Count 復(fù)雜度

時(shí)間O(n) 空間O(1)

思路

如果對時(shí)間復(fù)雜度沒有要求，這個(gè)方法是實(shí)現(xiàn)起來最簡單的，我們只需要從下往上依次數(shù)(n+m)/2個(gè)元素即可。由于兩個(gè)數(shù)組都已經(jīng)排序，我們可以使用兩個(gè)指針指向數(shù)組“底部”，通過比較兩個(gè)數(shù)組“底部”的元素大小來決定計(jì)哪一個(gè)元素，同時(shí)將其所在數(shù)組的指針“向上”移一位。為了方便處理總元素為偶數(shù)的情況，這里將找中位數(shù)變成找第k小的元素。

注意

計(jì)數(shù)的循環(huán)是用來找到第k-1個(gè)元素的，最后return的時(shí)候再判斷第k個(gè)元素是哪一個(gè)

在每次計(jì)數(shù)的循環(huán)中要先判斷兩個(gè)數(shù)組指針是否超界，在最后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 復(fù)雜度

時(shí)間O(log(m+n)) 空間O(1)

思路

題目要求O(log(m+n))的時(shí)間復(fù)雜度，一般來說都是分治法或者二分搜索。首先我們先分析下題目，假設(shè)兩個(gè)有序序列共有n個(gè)元素（根據(jù)中位數(shù)的定義我們要分兩種情況考慮），當(dāng)n為奇數(shù)時(shí)，搜尋第(n/2+1)個(gè)元素，當(dāng)n為偶數(shù)時(shí)，搜尋第(n/2+1)和第(n/2)個(gè)元素，然后取他們的均值。進(jìn)一步的，我們可以把這題抽象為“搜索兩個(gè)有序序列的第k個(gè)元素”。如果我們解決了這個(gè)k元素問題，那中位數(shù)不過是k的取值不同罷了。

那如何搜索兩個(gè)有序序列中第k個(gè)元素呢，這里又有個(gè)技巧。假設(shè)序列都是從小到大排列，對于第一個(gè)序列中前p個(gè)元素和第二個(gè)序列中前q個(gè)元素，我們想要的最終結(jié)果是：p+q等于k-1,且一序列第p個(gè)元素和二序列第q個(gè)元素都小于總序列第k個(gè)元素。因?yàn)榭傂蛄兄?，必然有k-1個(gè)元素小于等于第k個(gè)元素。這樣第p+1個(gè)元素或者第q+1個(gè)元素就是我們要找的第k個(gè)元素。

所以，我們可以通過二分法將問題規(guī)?？s小，假設(shè)p=k/2-1，則q=k-p-1，且p+q=k-1。如果第一個(gè)序列第p個(gè)元素小于第二個(gè)序列第q個(gè)元素，我們不確定二序列第q個(gè)元素是大了還是小了，但一序列的前p個(gè)元素肯定都小于目標(biāo)，所以我們將第一個(gè)序列前p個(gè)元素全部拋棄，形成一個(gè)較短的新序列。然后，用新序列替代原先的第一個(gè)序列，再找其中的第k-p個(gè)元素（因?yàn)槲覀円呀?jīng)排除了p個(gè)元素，k需要更新為k-p），依次遞歸。同理，如果第一個(gè)序列第p個(gè)元素大于第二個(gè)序列第q個(gè)元素，我們則拋棄第二個(gè)序列的前q個(gè)元素。遞歸的終止條件有如下幾種：

較短序列所有元素都被拋棄，則返回較長序列的第k個(gè)元素（在數(shù)組中下標(biāo)是k-1）

一序列第p個(gè)元素等于二序列第q個(gè)元素，此時(shí)總序列第p+q=k-1個(gè)元素的后一個(gè)元素，也就是總序列的第k個(gè)元素

注意

每次遞歸不僅要更新數(shù)組起始位置（起始位置之前的元素被拋棄），也要更新k的大?。鄢粧仐壍脑兀?/p> 代碼 

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是較短的數(shù)組
        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];
        }
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/64391.html

相關(guān)文章

  • Leetcode-4 Median of Two Sorted Arrays

    摘要：解法解法應(yīng)該是最常見的一種解法，就是將兩個(gè)數(shù)組頭尾相加合并起來，然后重新排序，例如輸入兩個(gè)數(shù)組，合并之后變?yōu)?，然后求出中位?shù)。如果兩個(gè)數(shù)組長度和為偶數(shù)，那么中位數(shù)有兩個(gè)，否則只有一個(gè) 題目 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

    摘要：復(fù)雜度思路因?yàn)橐抑形粩?shù)，又是在兩個(gè)的數(shù)組里面。所以考慮用二分法。二分法經(jīng)常適合的接下來考慮如何二分。然后對和進(jìn)行比較，記為和。所以為了縮小搜索范圍，我們可以扔掉這些數(shù)，在的剩下來的數(shù)中和的數(shù)組中接著找。說明中沒有個(gè)數(shù)可以尋找。 Leetcode[4] Median of two sorted arrays There are two sorted arrays nums1 and n...

    sarva 評論0 收藏0

  • 【leetcode長跑】開個(gè)頭 Median of Two Sorted Arrays

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

    荊兆峰 評論0 收藏0

  • [LintCode/LeetCode] Median of two Sorted Arrays

    摘要：由于要求的時(shí)間，所以選擇二分法。思路是找到兩個(gè)數(shù)組合并起來的第個(gè)元素。這樣只需計(jì)算兩個(gè)數(shù)組的中位數(shù)是第幾個(gè)元素，代入功能函數(shù)即可。據(jù)此，根據(jù)二分法的性質(zhì)，我們在遞歸時(shí)可以將前即個(gè)元素排除。 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 兩排序數(shù)組的中位數(shù)

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

    wudengzan 評論0 收藏0

發(fā)表評論

0條評論

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