Re: [問題] 給定n個排好序的整數陣列 找中位數
看板Prob_Solve (計算數學 Problem Solving)作者dreamoon (大笨蛋小月唷!)時間10年前 (2014/10/15 12:56)推噓1(1推 0噓 0→)留言1則, 1人參與討論串5/8 (看更多)
※ 引述《DJWS (...)》之銘言：
: 依序掃描n個中位數 O(n)
: 比x小(大)的中位數
: 其所對應的陣列，預計刪除小(大)的那一半
: 也就是 low = (low + high) / 2 + 1; O(1)
: (或者 high = (low + high) / 2 - 1;)
: 預計更新陣列大小為 size = high - low + 1 O(1)
: 累計欲刪除的元素數量 y (小的那些) O(1)
: 如果第k個元素小於等於 y，那麼就刪除最大的那 1/4，下個回合找第 k 小的元素
: 否則就刪除最小的那 1/4，下個回合找第 k = Σsize - y 大的元素
對於這裡我有點困惑
若k<=y，刪除叫大的那些數是沒問題的，因為那些數一定比第k個數還大
但是當k>y時，真的能刪除較小的那一部分嘛?
例如說現在有7*7的矩陣
1, 2, 3, 4, 5, 6, 7
8, 9,10,11,12,13,14
15,16,17,18,19,20,21
22,23,24,25,26,27,28
29,30,31,32,33,34,35
36,37,38,39,40,41,42
43,44,45,46,47,48,49
並且我要找的數是第17小的數
但比較小的那部分卻只有16個數
於是按照這個演算法我們就會把真正的第17小的數給移除了0.0(我沒理解錯的話...)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.28.238
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1413348969.A.3EC.html
推
10/15 13:33, , 1F
10/15 13:33, 1F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
