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

資訊專欄INFORMATION COLUMN

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

荊兆峰 / 3049人閱讀

摘要：自第一篇收集向的文章發布后，近年半沒更新這個專欄了。今天是分類中第一個的，叫做。不過這樣需要兩個數組各掃一遍，然而我們的目的只是要取到中間值，似乎并不用完整的掃一遍。那么也就意味著，我們最終要記錄的值可能是兩個。

大家好，我叫張小豬。

自第一篇收集向的文章發布后，近 1 年半沒更新這個專欄了。最近面試中發現將近 60% 的候選人對于 bubble sort 面露難色，于是心悸于自己也忘記了很多大學的內容，遂有時間就寫寫 leetcode 好了，也不荒廢當初開了這個地方。路途遙遠，且行且珍惜。

今天是 Algorithms 分類中第一個 Hard 的，叫做 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)).

題目描述內容比較少，大意就是提供兩個有序數組，需要找到這兩個數組的中間值。
給了兩個例子:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

看完描述和例子后，第一反應就是合并兩個數組，然后找到中間位置即可。不過這樣需要兩個數組各掃一遍，然而我們的目的只是要取到中間值，似乎并不用完整的掃一遍。那就按照這個思路看看吧。

首先，根據例子可以看出，偶數和奇數個長度對于最終結果的計算是會有影響的。即奇數個我們能直接取到中間值，而偶數個需要取到最靠近中間的兩個值然后取平均數。那么也就意味著，我們最終要記錄的值可能是兩個。
然后，由于兩個數組都是有序的，那么他們的中間值索引其實就是做合并操作過程中的索引。

基于以上兩點，我們得到要做的事情是:

計算中間值的索引

做有序數組合并

得到結果

那么開始寫代碼吧（吐槽一下 leetcode 的編輯器并不太好用）:

var findMedianSortedArrays = function(nums1, nums2) {
    var sumLen = nums1.length + nums2.length,
        targetLen = sumLen >>> 1,
        loop = targetLen + 1,
        i = 0, // for num1 index
        j = 0, // for num2 index
        x, y;

    while (loop--) {
        x = y;
        if (nums1[i] === undefined) {
            y = nums2[j++]
        } else if (nums2[j] === undefined) {
            y = nums1[i++];
        } else if (nums1[i] < nums2[j]) {
            y = nums1[i++];
        } else {
            y = nums2[j++];
        }
    }

    return targetLen << 1 === sumLen ? (x + y) / 2 : y;
};

Test case 通過后連續提交了幾次，時間在 beats 85% 左右浮動，最低 72%，最高 97%，算是可以接受吧。

想想最近快要到雙 11 了，別人都是買包買衣買香水、家具電器旅行飛，小豬只是連著關注了幾天顯卡和 CPU，還舍不得剁手。哎，說多了都是淚啊，還是洗洗豬鼻子睡了吧。。。

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/89481.html

相關文章

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

  • [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] Median of Two Sorted Arrays 有序數組中位數

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

    wuaiqiu 評論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元查看
<