最新消息

關於五倍還有更多你可以發掘的,都在這邊說給你知!

Thumb 111

FIND THE RUNNING MEDIAN - 演算法例:會跑的中位數~改變人生從解題開始~

By tsw 12月14日 17:42

簡單複習一下中位數以免你忘了

  

中位數(又稱中值,英語:Median),統計學中的專有名詞,代表一個樣本、種群或機率分布中的一個數值,其可將數值集合劃分爲相等的上下兩部分。對於有限的數集,可以通過把所有觀察值高低排序後找出正中間的一個作爲中位數。如果觀察值有偶數個,則中位數不唯一,通常取最中間的兩個數值的平均數作爲中位數。

  

假設今天龍哥開了一場 VIP 握手會,來參加的 VIP 共有五位,年齡由小到大分別是 12, 17, 21, 29, 38,那我們可以說 VIP 的年齡中位數是 21。 若是龍哥晚上又開了一場 VIP 床上聊天會,來參加的 VIP 共有四位,年齡由小到大分別是 20, 24, 25, 60,那我們可以說 VIP 的年齡中位數是 24.5。

  

怎麼用演算法解?

  

  1. 將 input 的資料排序過一遍
  2. 若 input 項目數量(N)是奇數,取第 ceil(N/2) 項為中位數
  3. 若 input 項目數量(N)是偶數,取第 N/2 項與 N/2 + 1 項相加再除以二為中位數

  

求中位數的演算法題都是送分題?

  

對於大部分有念過資訊科系的同學來說,中位數的題目都是十分簡單的,最常出現在大一學生的考卷上,考驗大學新鮮人們是否有專心在聽課堂上介紹的排序演算法。 所以...

  

對,中位數的演算法題都是送分題!

  

我一直是這樣認為的

  

直到我看到下面這題為止。

  

FIND THE RUNNING MEDIAN link

  

有興趣的朋友們可以點上面的那個連結去寫寫看,挑戰通過全部的 test case,成功的人就可以左轉離開了,沒成功的人請看下面詳細說明。

  

題目說明

  

  • 你會收到一連串未排序過的正整數,除了第一個數字代表樣本總數量之外,其他的數字都是樣本
  • 請你每收到一個樣本的時候,從所有你收到的樣本中找出一個中位數

  

解題說明

  

假設使用時間複雜度 O(nlogn) 等級的排序演算法配上原本的解題邏輯來解,最終解法時間複雜度會超過 O(n^2logn) ,這樣是過不了 hackerrank 上最後三個 test case 的。

  

(如果要通過 amazon 面試的第一關,必須全過)

  

那該怎麼辦?

  

大一的程式設計不夠用?只好出動大二的資料結構了!

  

重新思考整個題目之後,會發現我們只要設計一個二元樹結構,可讓我們直接取得中位數就行了。 典型的二元樹的插入動作時間複雜度是 O(logn),讀取動作時間複雜度是 O(1),所以我們最終可以獲得 O(nlogn) 的解法。

  

由於我們取出的時後有可能需要一次取出兩個數字,

  

所以我們需要兩棵樹:

  • 一棵小樹專門放小於中位數的值
  • 一棵大樹專門放大於中位數的值

  

這樣小樹可以直接使用 max heap (頭是堆中最大值的堆積),大樹可以直接使用 min heap (頭是堆中最小值的堆積)。

  

同時依照中位數的定義,小樹根大樹的高度應該要一樣,所以當兩棵樹高度差超過 1 的時候,需要取出高樹的頭插入低樹裡面(聽起來怪怪的(汗))。

  

取出頭的動作跟插入一樣都是 O(logn)

  

這樣一來,中位數就十分容易取得了:

  • 當兩棵樹一樣高的時候,兩棵樹的頭相加除以 2 就是中位數。
  • 當兩棵樹不一樣高的時候,高樹的頭就是中位數。

  

時間複雜度:

  • 插入新樣本:T(3logn + 1)
  • 讀取中位數:T(2)
  • 整體結果:O(nlogn)

  

將上面的想法實作出來之後塞進 hackerrank 裡面跑,嗯,全過,恭喜各位可以通過 amazon 面試的第一關了!

  

結論

  

以結果來說,這題的滿分關鍵是堆積,而很多人學了各種好用的樹之後,就把堆積給忘了,因此沒辦法獲得滿分、在面試上敗陣下來, 因此這題可以說是包著求中位數皮的陷阱題,在這邊分享給各位,希望對各位的人生能有所幫助。

comments powered by Disqus « 回文章列表