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