討論串[問題] 給定n個排好序的整數陣列 找中位數
共 8 篇文章
內容預覽:
問題：給定 n 個已排序整數陣列，每個陣列長度為 n. 找出 n^2 個元素中的中位數。. 在網路上有找到幾個討論. http://ppt.cc/PMvU. http://ppt.cc/JE1s. (這是變形，給定一個n by n矩陣，每行每列都排序，找中位數). 但是我覺得他們的解法到最後都變成O
(還有151個字)
內容預覽:
應該很難吧！. 資料有 n^2 筆，然後時間複雜度是 O(n^2)，基本上已經是 linear time. 要低於線性時間. 要嘛略過一些資料. 要嘛問題本身有很強的數學性質，可以直接推導答案. 在這個問題當中，上面兩種策略似乎都行不太通. 考慮 median-of-median algorithm
(還有345個字)
內容預覽:
我有想到一個類似的方法，先把每列median找出來，總共有 n 個。. 找出這 n 個元素的最大值 max 和最小值 min 及其所在的列max_i, min_i。. 然後可以把max_i或是min_i列中刪除一半的元素 （這邊需要case分析解決base case）. 這樣每回合至少會有一列的大小
(還有151個字)
內容預覽:
昨天睡覺時用力想了一陣. 事實上不需要跑 binary search，也不必跑 partition. 這邊重新整理一下. 給定 n 個長度 n 已排序陣列，找第 k 小的元素. 每個陣列都有兩個指標 low = 0 和 high = n-1 O(n). 每個陣列的大小 size = high - l
(還有861個字)
內容預覽:
對於這裡我有點困惑. 若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. 2
(還有124個字)