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

資訊專欄INFORMATION COLUMN

拿起算法的鋼筆: 找出兩個(gè)有序數(shù)組的中位數(shù)

summerpxy / 983人閱讀

摘要:給定兩個(gè)大小為和的有序數(shù)組和題目請(qǐng)你找出這兩個(gè)有序數(shù)組的中位數(shù),并且要求算法的時(shí)間復(fù)雜度為。一般我們的二分搜索是一個(gè)有序數(shù)組,查找元素,每一次查找,把搜索范圍縮減一半。

給定兩個(gè)大小為 m 和 n 的有序數(shù)組?nums1 和?nums2

題目:請(qǐng)你找出這兩個(gè)有序數(shù)組的中位數(shù),并且要求算法的時(shí)間復(fù)雜度為?O(log(m + n))。

你可以假設(shè)?nums1?和?nums2?不會(huì)同時(shí)為空。

示例 1:

nums1 = [1, 3]

nums2 = [2]

則中位數(shù)是 2.0

示例 2:

nums1 = [1, 2]

nums2 = [3, 4]

則中位數(shù)是 (2 + 3)/2 = 2.5

分析: 常規(guī)做法, 是 O(m+n)

兩個(gè)有序數(shù)組,合并成一個(gè)有序數(shù)組,取中位數(shù),
思路很清晰

這里只要取中位數(shù),只要保證,這個(gè)數(shù)字左邊的元素個(gè)數(shù)( 數(shù)組一左邊 i 個(gè)+數(shù)組二左邊 j 個(gè) )與右邊的元素個(gè)數(shù)相等,這個(gè)數(shù)字左邊的元素都小于右邊的元素,

就可以認(rèn)為,這個(gè)數(shù)字是我們想要的

先分片, 保證找到的中位數(shù),這個(gè)數(shù)字左邊的元素個(gè)數(shù)( 數(shù)組一左邊 i 個(gè)+數(shù)組二左邊 j 個(gè) )與右邊的元素個(gè)數(shù)相等

因?yàn)槭侵虚g位置的數(shù)字,
如果第一個(gè)數(shù)組 nums1 取 i 個(gè),( 0 <= i <= m ),
那么第二個(gè)數(shù)組 nums2 里面取 j 個(gè), ( 0 <= j <= n ),

i 與 j 滿足一定的關(guān)系 i + j = ( m + n )/2 , 或者 i + j = ( m + n + 1)/2 , 因?yàn)? m + n 可能是奇數(shù),也可能是偶數(shù)。
那么 j = ( m + n + 1 ) / 2 - i

再取值,這個(gè)數(shù)字左邊的元素都小于右邊的元素

i 和 j 把兩個(gè)數(shù)組,各分成兩片,出現(xiàn)了四個(gè)關(guān)鍵的數(shù)字,

數(shù)組一左邊最大,num1LeftMax

數(shù)組一右邊最小,num1RightMin

數(shù)組二左邊最大,num2LeftMax

數(shù)組二右邊最小,num2RightMin

如果 num1LeftMax <= num2RightMin, num2LeftMax <= num1RightMin, 就找到我們想要的中位數(shù)了,因?yàn)?num1 是有序數(shù)組,num1LeftMax 當(dāng)然小于 num1RightMin,同樣的 num2LeftMax < num2RightMin

O(m), 因?yàn)檫@就是二分搜索,搜索條件不是很直接

為什么是 O(m), 因?yàn)檫@就是二分搜索。

一般我們的二分搜索是一個(gè)有序數(shù)組,查找元素,每一次查找,把搜索范圍縮減一半。通過移動(dòng)上邊界和下邊界

就是比較條件相對(duì)簡單,直接比元素大小

這道題其他與基礎(chǔ)的二分查找一致, 比較條件有些變化

如果 num1LeftMax > num2RightMin, 數(shù)字一左邊的大了,就是 i 大了,就要移動(dòng)右邊界,就是右邊界變小

(左邊界只能右移,只能變大。右邊界只能左移,只能變?。?/p>

其他情況,類似處理

拿起算法的鋼筆,跑一遍

示例 3:

nums1 = [ 1, 3,8,9,15 ]

nums2 = [ 7, 11, 18, 19, 21,25 ]

中位數(shù)是 11

左邊有 5 個(gè)元素, m = 5,

右邊有 6 個(gè), n = 6

數(shù)組一右邊最小,num1RightMin < 數(shù)組二左邊最大,num2LeftMax
就是 i 小了,左邊界右移, low = 3

現(xiàn)在滿足要求了,m + n 是奇數(shù),左邊多一個(gè),選數(shù)組一左邊最大和數(shù)組二左邊最大中較大的,就是 11

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

示例 4:

nums1 = [ 23, 26,31,35 ]

nums2 = [ 3, 5, 7, 9, 11,16 ]

中位數(shù)是 13.5, 11 和 16 的平均值

左邊有 4 個(gè)元素, m = 4,

右邊有 6 個(gè), n = 6

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

左邊一個(gè)元素都不要,默認(rèn)數(shù)組一左邊最大為負(fù)無窮,num1LeftMax = Number.MIN_SAFE_INTEGER,

現(xiàn)在滿足要求了,m + n 是偶數(shù),找出中間兩個(gè) 11 與 16,求平均值為 13.5

PS: 個(gè)人看,看書和看算法動(dòng)畫,不錯(cuò),就是少了一點(diǎn)參與感。
拿起鋼筆,寫寫畫畫,需要保證結(jié)果一致嘛,我感覺,理解的好一些
代碼如下:

選短的數(shù)組處理,處理快,還保證了 j 一定大于 0 (因?yàn)?n > m),避免了一些邏輯處理。

里面處理了一些邊界條件, i = 0, 第一個(gè)數(shù)組左邊一個(gè)元素都不要,i = m, 第一個(gè)數(shù)組右邊一個(gè)元素都不要

m + n 的值是奇數(shù),這個(gè)好處理一點(diǎn),只需要找出一個(gè)元素

m + n 的值是偶數(shù),需要找出兩個(gè)元素

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;
};
我還喜歡看視頻,有一個(gè) youtube ,鏈接是 https://www.youtube.com/watch... .

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

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

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

相關(guān)文章

  • LeetCode4.尋找兩個(gè)有序數(shù)組位數(shù) JavaScript

    摘要:尋找兩個(gè)有序數(shù)組的中位數(shù)給定兩個(gè)大小為和的有序數(shù)組和。請(qǐng)你找出這兩個(gè)有序數(shù)組的中位數(shù),并且要求算法的時(shí)間復(fù)雜度為。你可以假設(shè)和不會(huì)同時(shí)為空。示例則中位數(shù)是示例則中位數(shù)是答案參考排序中位數(shù) LeetCode4.尋找兩個(gè)有序數(shù)組的中位數(shù) JavaScript 給定兩個(gè)大小為m和n的有序數(shù)組nums1和nums2。請(qǐng)你找出這兩個(gè)有序數(shù)組的中位數(shù),并且要求算法的時(shí)間復(fù)雜度為 O(log(m +...

    habren 評(píng)論0 收藏0
  • JS算法題之leetcode(1~10)

    摘要:先去空白,去掉空白之后取第一個(gè)字符,判斷正負(fù)符號(hào),若是英文直接返回,若數(shù)字則不取。回文數(shù)題目描述判斷一個(gè)整數(shù)是否是回文數(shù)。回文數(shù)是指正序從左向右和倒序從右向左讀都是一樣的整數(shù)。 JS算法題之leetcode(1~10) 前言 一直以來,前端開發(fā)的知識(shí)儲(chǔ)備在數(shù)據(jù)結(jié)構(gòu)以及算法層面是有所暫缺的,可能歸根于我們的前端開發(fā)的業(yè)務(wù)性質(zhì),但是我認(rèn)為任何的編程崗位都離不開數(shù)據(jù)結(jié)構(gòu)以及算法。因此,我作為...

    SoapEye 評(píng)論0 收藏0
  • 一些前端算法詳解 --- (不定時(shí)更新)

    摘要:也稱縮小增量排序,是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方法因於年提出而得名。 前言 因?yàn)楸容^隨心所欲,所以我不按難度分享算法,所以你們會(huì)看到有時(shí)候順序有變化,因?yàn)槲野l(fā)表的時(shí)候會(huì)按照難度修改下位置,盡量讓你們看的時(shí)候能從簡單開始,以后每次更新都加個(gè)更新時(shí)間好了,讓你們知道我進(jìn)度.新增計(jì)時(shí)函數(shù)直觀對(duì)比效率并且因?yàn)橘Y料比較雜,很多都是我個(gè)人理解說法,如果有發(fā)...

    Baaaan 評(píng)論0 收藏0
  • 前端 100 問:能搞懂80%請(qǐng)把簡歷給我

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

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

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

0條評(píng)論

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