拿起算法的鋼筆: 找出兩個有序數組的中位數

summerpxy 發布于2019-08-26 10:28 / 938人閱讀

摘要：給定兩個大小為和的有序數組和題目請你找出這兩個有序數組的中位數，并且要求算法的時間復雜度為。一般我們的二分搜索是一個有序數組，查找元素，每一次查找，把搜索范圍縮減一半。

給定兩個大小為 m 和 n 的有序數組?nums1 和?nums2

題目：請你找出這兩個有序數組的中位數，并且要求算法的時間復雜度為?O(log(m + n))。

你可以假設?nums1?和?nums2?不會同時為空。

示例 1:

nums1 = [1, 3]nums2 = [2]
則中位數是 2.0

示例 2:

nums1 = [1, 2]nums2 = [3, 4]
則中位數是 (2 + 3)/2 = 2.5

分析： 常規做法，是 O(m+n)

兩個有序數組，合并成一個有序數組，取中位數，
思路很清晰

這里只要取中位數，只要保證，這個數字左邊的元素個數（數組一左邊 i 個+數組二左邊 j 個）與右邊的元素個數相等，這個數字左邊的元素都小于右邊的元素，

就可以認為，這個數字是我們想要的

先分片, 保證找到的中位數，這個數字左邊的元素個數（數組一左邊 i 個+數組二左邊 j 個）與右邊的元素個數相等

因為是中間位置的數字，
如果第一個數組 nums1 取 i 個，（ 0 <= i <= m ）,
那么第二個數組 nums2 里面取 j 個, （ 0 <= j <= n ）,

i 與 j 滿足一定的關系 i + j = ( m + n )/2 , 或者 i + j = ( m + n + 1)/2 , 因為 m + n 可能是奇數，也可能是偶數。
那么 j = ( m + n + 1 ) / 2 - i

再取值，這個數字左邊的元素都小于右邊的元素

i 和 j 把兩個數組，各分成兩片，出現了四個關鍵的數字，

數組一左邊最大，num1LeftMax

數組一右邊最小，num1RightMin

數組二左邊最大，num2LeftMax

數組二右邊最小，num2RightMin

如果 num1LeftMax <= num2RightMin, num2LeftMax <= num1RightMin, 就找到我們想要的中位數了，因為 num1 是有序數組，num1LeftMax 當然小于 num1RightMin，同樣的 num2LeftMax < num2RightMin

O(m), 因為這就是二分搜索，搜索條件不是很直接

為什么是 O(m), 因為這就是二分搜索。

一般我們的二分搜索是一個有序數組，查找元素，每一次查找，把搜索范圍縮減一半。通過移動上邊界和下邊界

就是比較條件相對簡單，直接比元素大小

這道題其他與基礎的二分查找一致，比較條件有些變化

如果 num1LeftMax > num2RightMin, 數字一左邊的大了，就是 i 大了，就要移動右邊界，就是右邊界變小

（左邊界只能右移，只能變大。右邊界只能左移，只能變小）

其他情況，類似處理

拿起算法的鋼筆，跑一遍

示例 3:

nums1 = [ 1, 3，8，9，15 ]nums2 = [ 7， 11， 18， 19， 21，25 ]

中位數是 11

左邊有 5 個元素， m = 5,

右邊有 6 個， n = 6

數組一右邊最小，num1RightMin < 數組二左邊最大，num2LeftMax
就是 i 小了，左邊界右移， low = 3

現在滿足要求了，m + n 是奇數，左邊多一個，選數組一左邊最大和數組二左邊最大中較大的，就是 11

拿起算法的鋼筆，再跑一遍，為了印象深刻

示例 4:

nums1 = [ 23, 26，31，35 ]nums2 = [ 3， 5， 7， 9， 11，16 ]

中位數是 13.5， 11 和 16 的平均值

左邊有 4 個元素， m = 4,

右邊有 6 個， n = 6

數組一左邊最大，num1LeftMax > 數組二右邊最小，num2RightMin
就是 i 大了，右邊界左移, high = 1

左邊一個元素都不要，默認數組一左邊最大為負無窮，num1LeftMax = Number.MIN_SAFE_INTEGER,

現在滿足要求了，m + n 是偶數，找出中間兩個 11 與 16，求平均值為 13.5

PS: 個人看，看書和看算法動畫，不錯，就是少了一點參與感。
拿起鋼筆，寫寫畫畫，需要保證結果一致嘛，我感覺，理解的好一些

代碼如下：

選短的數組處理，處理快，還保證了 j 一定大于 0 （因為 n > m），避免了一些邏輯處理。

里面處理了一些邊界條件， i = 0, 第一個數組左邊一個元素都不要，i = m, 第一個數組右邊一個元素都不要

m + n 的值是奇數，這個好處理一點，只需要找出一個元素

m + n 的值是偶數，需要找出兩個元素

var findMedianSortedArrays = function (nums1, nums2) {
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1]
    }
    const arr1Length = nums1.length, arr2Length = nums2.length;
    let low = 0, high = arr1Length;
    const halfLen = Math.floor((arr1Length + arr2Length + 1) / 2);

    while (low <= high) {
        let i = Math.floor((low + high) / 2); 
        let j = halfLen - i;
        let num1LeftMax = i == 0 ? Number.MIN_SAFE_INTEGER : nums1[i - 1]
        let num1RightMin = i == arr1Length ? Number.MAX_SAFE_INTEGER : nums1[i]
        let num2LeftMax = j == 0 ? Number.MIN_SAFE_INTEGER : nums2[j - 1]
        let num2RightMin = j == arr2Length ? Number.MAX_SAFE_INTEGER : nums2[j]
        if (num1LeftMax <= num2RightMin && num2LeftMax <= num1RightMin) {
            var answer = 0
            if (Math.round((arr1Length + arr2Length) % 2) == 1) {
                answer = Math.max(num1LeftMax, num2LeftMax)
            }
            else {
                // Math.round((arr1Length + arr2Length) % 2) == 0
                let leftMax = Math.max(num1LeftMax, num2LeftMax)
                let rightMin = Math.min(num1RightMin, num2RightMin)
                answer = (leftMax + rightMin) / 2
            }
            return answer
        }
        else if (num1LeftMax > num2RightMin) {
            high = i - 1
        }
        else { // num2LeftMax > num1RightMin
            low = i + 1
        }
    }
    return 0;
};

我還喜歡看視頻，有一個 youtube ,鏈接是 https://www.youtube.com/watch... .

本文可以作為該視頻和 Leatcode 官方題解的補充，官方題解: https://leetcode.com/problems...

云服務器 GPU云服務器字符串轉換為多位數的算法 linux 找出的數據 cp linux+找出的數據+cp java 集合有序的

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

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

LeetCode4.尋找兩個有序數組的中位數 JavaScript

摘要：尋找兩個有序數組的中位數給定兩個大小為和的有序數組和。請你找出這兩個有序數組的中位數，并且要求算法的時間復雜度為。你可以假設和不會同時為空。示例則中位數是示例則中位數是答案參考排序中位數 LeetCode4.尋找兩個有序數組的中位數 JavaScript 給定兩個大小為m和n的有序數組nums1和nums2。請你找出這兩個有序數組的中位數，并且要求算法的時間復雜度為 O(log(m +...

habren 2019-08-23 14:46 評論0 收藏0
JS算法題之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一個字符，判斷正負符號，若是英文直接返回，若數字則不取。回文數題目描述判斷一個整數是否是回文數。回文數是指正序從左向右和倒序從右向左讀都是一樣的整數。 JS算法題之leetcode(1~10) 前言一直以來，前端開發的知識儲備在數據結構以及算法層面是有所暫缺的，可能歸根于我們的前端開發的業務性質，但是我認為任何的編程崗位都離不開數據結構以及算法。因此，我作為...

SoapEye 2019-08-26 10:44 評論0 收藏0
一些前端算法詳解 --- (不定時更新)

摘要：也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因於年提出而得名。前言因為比較隨心所欲,所以我不按難度分享算法,所以你們會看到有時候順序有變化,因為我發表的時候會按照難度修改下位置,盡量讓你們看的時候能從簡單開始,以后每次更新都加個更新時間好了,讓你們知道我進度.新增計時函數直觀對比效率并且因為資料比較雜,很多都是我個人理解說法,如果有發...

Baaaan 2019-08-26 10:35 評論0 收藏0
前端 100 問：能搞懂80%的請把簡歷給我

摘要：解析第題第題為什么的和的中不能做異步操作解析第題第題京東下面代碼中在什么情況下會打印解析第題第題介紹下及其應用。盡量減少操作次數。解析第題第題京東快手周一算法題之兩數之和給定一個整數數組和一個目標值，找出數組中和為目標值的兩個數。引言半年時間，幾千人參與，精選大廠前端面試高頻 100 題，這就是「壹題」。在 2019 年 1 月 21 日這天，「壹題」項目正式開始，在這之后每個工...

Scott 2019-08-23 18:35 評論0 收藏0