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

資訊專欄INFORMATION COLUMN

Leetcode[4] Median of two sorted arrays

sarva / 2706人閱讀

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

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 two sorted arrays. The overall run time
complexity should be O(log (m+n)).


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
Binary search

復(fù)雜度
O(lg(m + n))

思路
因?yàn)橐抑形粩?shù)，又是在兩個(gè)sorted的數(shù)組里面。所以考慮用二分法。（二分法經(jīng)常適合sorted的array).
接下來(lái)考慮如何二分。
假設(shè)第k個(gè)數(shù)是我們要找的中位數(shù)，那么前k-1個(gè)數(shù)應(yīng)該都比這個(gè)第k個(gè)數(shù)要小。后面的數(shù)都比這個(gè)第k個(gè)數(shù)大。（像變形的用二分法找第K個(gè)數(shù)）。
如果我們每次在a數(shù)組中找前(k/2) = m個(gè)數(shù)，在b數(shù)組中找剩下的(k-k/2) = n個(gè)數(shù)。然后對(duì)a[p + k/2 - 1]和b[q + k - k/2 -1]進(jìn)行比較，記為a[i]和b[j]。

a[i] < b[j]： 說(shuō)明我們可以扔掉0-i之間的（i+ 1）個(gè)數(shù)。為什么？
因?yàn)閍數(shù)組中的前m個(gè)數(shù)的最大值都比b數(shù)組中的前n個(gè)數(shù)要小，那么這前m個(gè)數(shù)一定是在我們想要的中位數(shù)之前的，并且對(duì)找到中位數(shù)沒(méi)有說(shuō)明影響。所以為了縮小搜索范圍，我們可以扔掉這些數(shù)，在a的剩下來(lái)的數(shù)中和b的數(shù)組中接著找。

i>=a.length: 說(shuō)明a中沒(méi)有m個(gè)數(shù)可以尋找。那么第K個(gè)數(shù)要么在b剩下的數(shù)組[n ~ b.length]中，要么就在a的前m個(gè)數(shù)中。

一直搜索到什么時(shí)候?yàn)橹鼓兀?br>k=1代表的是，當(dāng)前的這個(gè)是就是我們想要的值，我們應(yīng)該在如何選擇? Math.min(a[p], b[q]).

if(a[i] < b[j]) {
  search（a[right], b[0], k - m);
} else {
  search (a[0], b[right], k - n);
}

我們從找第K個(gè)數(shù)開(kāi)始，一直到K=1，每次扔掉一部分?jǐn)?shù) k /2，所以時(shí)間復(fù)雜度是log(k).
K=(M + N) / 2, 所以時(shí)間復(fù)雜度是log(m + n)

代碼

class Solution {
    // 其實(shí)找的是第k個(gè)值。
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        if(len % 2 == 0) {
            return findKthNumberInTwoArray(nums1, nums2, 0, 0, len / 2) / 2 
                + findKthNumberInTwoArray(nums1, nums2, 0, 0, len / 2 + 1) / 2;
        } else {
            return findKthNumberInTwoArray(nums1, nums2, 0, 0, len / 2 + 1);
        }     
    }
    
    // p is the start index of nums1, q is the start index of nums2, we wanna find the kth number 
    // in both num1 & nums2
    public double findKthNumberInTwoArray(int[] nums1, int[] nums2, int p, int q, int k) {
        if(p >= nums1.length) return nums2[q + k - 1];
        if(q >= nums2.length) return nums1[p + k - 1];
        if(k == 1) return Math.min(nums1[p], nums2[q]);
        
        int m = k / 2, n = k - m;
        // 因?yàn)楫?dāng)a數(shù)組沒(méi)有中這個(gè)數(shù)的時(shí)候，說(shuō)明第k一定在b數(shù)組剩余的數(shù)中和a數(shù)組的剩余數(shù)組中的一個(gè)。
        int aVal = Integer.MAX_VALUE, bVal = Integer.MAX_VALUE;
        if(p + m - 1 < nums1.length) aVal = nums1[p + m - 1];
        if(q + n - 1 < nums2.length) bVal = nums2[q + n - 1];
        
        if(aVal < bVal) {
            return findKthNumberInTwoArray(nums1, nums2, p + m, q, k - m);
        } else {
            return findKthNumberInTwoArray(nums1, nums2, p, q + n, k - n);
        }
    }
}

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

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

相關(guān)文章

  • 【leetcode長(zhǎng)跑】開(kāi)個(gè)頭 Median of Two Sorted Arrays

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

    荊兆峰 評(píng)論0 收藏0

  • Leetcode-4 Median of Two Sorted Arrays

    摘要：解法解法應(yīng)該是最常見(jiàn)的一種解法，就是將兩個(gè)數(shù)組頭尾相加合并起來(lái)，然后重新排序，例如輸入兩個(gè)數(shù)組，合并之后變?yōu)椋缓笄蟪鲋形粩?shù)。如果兩個(gè)數(shù)組長(zhǎng)度和為偶數(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 評(píng)論0 收藏0

  • [LintCode/LeetCode] Median of two Sorted Arrays

    摘要：由于要求的時(shí)間，所以選擇二分法。思路是找到兩個(gè)數(shù)組合并起來(lái)的第個(gè)元素。這樣只需計(jì)算兩個(gè)數(shù)組的中位數(shù)是第幾個(gè)元素，代入功能函數(shù)即可。據(jù)此，根據(jù)二分法的性質(zhì)，我們?cè)谶f歸時(shí)可以將前即個(gè)元素排除。 Problem There are two sorted arrays A and B of size m and n respectively. Find the median of the tw...

    vvpvvp 評(píng)論0 收藏0

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

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

    wudengzan 評(píng)論0 收藏0

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

    摘要：最新解法及思路有兩個(gè)有序數(shù)組和，他們的大小各是和，請(qǐng)找出這兩個(gè)數(shù)組所有數(shù)的中位數(shù)，總得時(shí)間復(fù)雜度不超過(guò)歸并計(jì)數(shù)法復(fù)雜度時(shí)間空間思路如果對(duì)時(shí)間復(fù)雜度沒(méi)有要求，這個(gè)方法是實(shí)現(xiàn)起來(lái)最簡(jiǎn)單的，我們只需要從下往上依次數(shù)個(gè)元素即可。 Median of Two Sorted Arrays 最新解法及思路：https://yanjia.li/zh/2018/11/... There are two...

    wuaiqiu 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

sarva

男|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<