LeetCode 004 Median of Two Sorted Arrays 詳細(xì)分析

題目鏈接:https://leetcode.com/problems/median-of-two-sorted-arrays/

我一直會(huì)卡在這道題上胞锰,在網(wǎng)上看了半個(gè)小時(shí)的博客,愣是沒(méi)看懂唾糯。后來(lái)看到 YouTube 上有一個(gè)印度大哥的講解,豁然開(kāi)朗。

印度大哥的視頻地址:Binary Search : Median of two sorted arrays of different sizes.

題目描述

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)).

You may assume nums1 and nums2 cannot be both empty.

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

題目分析

其實(shí)這道題我卡就卡在,一直沒(méi)有想清楚應(yīng)該如何劃分兩個(gè)數(shù)組迫悠。直接看LeetCode論壇上的答案,也一直沒(méi)有搞懂巩梢。本題只是想求中位數(shù),并不用管其他的數(shù)字艺玲。

那么核心就在于括蝠,如何劃分兩個(gè)數(shù)組,使得兩個(gè)數(shù)組組合起來(lái)后饭聚,成為一個(gè)在中位數(shù)附近相對(duì)有序的數(shù)組即可忌警。

具體實(shí)例分析

算法分析

定義兩個(gè)變量 partitionX、 partitionY秒梳,分別分割X數(shù)組和Y數(shù)組法绵,記為X1, X2, Y1, Y2。使得

len(X1) + len(Y1) == len(X2) + len(Y2)
或
len(X1) + len(Y1) == len(X2) + len(Y2) + 1

并且使得 max(X1) < min(Y2), max(Y1) < min(X2)酪碘,這樣數(shù)組就被完整地分成了兩部分朋譬。

如果兩個(gè)數(shù)組長(zhǎng)度的和是奇數(shù),那么必然是 max(X1, Y1)了兴垦;
如果兩個(gè)數(shù)組長(zhǎng)度的和是偶數(shù)徙赢,那么是 (max(X1, Y1) + min(X2, Y2)) / 2字柠。

代碼實(shí)現(xiàn)

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }

    int x = nums1.length, y = nums2.length;
    int low = 0, high = x;

    while (low <= high) {
        int partitionX = (low + high) / 2;
        int partitionY = (x + y + 1) / 2 - partitionX;

        int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
        int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];

        int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
        int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];

        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            if ((x + y) % 2 == 0) {
                return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0;
            } else {
                return Math.max(maxLeftX, maxLeftY);
            }
        } else if (minRightX < maxLeftY) {
            low = partitionX + 1;
        } else {
            high = partitionX - 1;
        }
    }

    throw new RuntimeException();
}

總結(jié)

這道題如果能把圖畫(huà)出來(lái),理解起來(lái)就很容易狡赐。但是這道題在LeetCode中的難度是hard窑业,因?yàn)榫帉?xiě)代碼并不容易,有很多邊界條件:

  1. 數(shù)組長(zhǎng)度的奇偶
  2. 移動(dòng)過(guò)程中枕屉,某個(gè)數(shù)組被切割后可能為空
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末常柄,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子搀擂,更是在濱河造成了極大的恐慌西潘,老刑警劉巖,帶你破解...
    沈念sama閱讀 212,454評(píng)論 6 493
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件哥倔,死亡現(xiàn)場(chǎng)離奇詭異秸架,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)咆蒿,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,553評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門(mén)东抹,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人沃测,你說(shuō)我怎么就攤上這事缭黔±眩” “怎么了阱驾?”我有些...
    開(kāi)封第一講書(shū)人閱讀 157,921評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵桌吃,是天一觀(guān)的道長(zhǎng)丐黄。 經(jīng)常有香客問(wèn)我饲齐,道長(zhǎng)钾怔,這世上最難降的妖魔是什么鳍刷? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 56,648評(píng)論 1 284
  • 正文 為了忘掉前任租漂,我火速辦了婚禮喇伯,結(jié)果婚禮上喊儡,老公的妹妹穿的比我還像新娘。我一直安慰自己稻据,他們只是感情好艾猜,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,770評(píng)論 6 386
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著捻悯,像睡著了一般匆赃。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上今缚,一...
    開(kāi)封第一講書(shū)人閱讀 49,950評(píng)論 1 291
  • 那天算柳,我揣著相機(jī)與錄音,去河邊找鬼姓言。 笑死埠居,一個(gè)胖子當(dāng)著我的面吹牛查牌,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播滥壕,決...
    沈念sama閱讀 39,090評(píng)論 3 410
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼纸颜,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了绎橘?” 一聲冷哼從身側(cè)響起胁孙,我...
    開(kāi)封第一講書(shū)人閱讀 37,817評(píng)論 0 268
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎称鳞,沒(méi)想到半個(gè)月后涮较,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,275評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡冈止,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,592評(píng)論 2 327
  • 正文 我和宋清朗相戀三年狂票,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片熙暴。...
    茶點(diǎn)故事閱讀 38,724評(píng)論 1 341
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡闺属,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出周霉,到底是詐尸還是另有隱情掂器,我是刑警寧澤,帶...
    沈念sama閱讀 34,409評(píng)論 4 333
  • 正文 年R本政府宣布俱箱,位于F島的核電站国瓮,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏狞谱。R本人自食惡果不足惜乃摹,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,052評(píng)論 3 316
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望跟衅。 院中可真熱鬧峡懈,春花似錦、人聲如沸与斤。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,815評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)撩穿。三九已至,卻和暖如春谒撼,著一層夾襖步出監(jiān)牢的瞬間食寡,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 32,043評(píng)論 1 266
  • 我被黑心中介騙來(lái)泰國(guó)打工廓潜, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留抵皱,地道東北人善榛。 一個(gè)月前我還...
    沈念sama閱讀 46,503評(píng)論 2 361
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像呻畸,于是被迫代替她去往敵國(guó)和親移盆。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,627評(píng)論 2 350