討論串[問題] 給定n個排好序的整數陣列 找中位數
共 8 篇文章
內容預覽:
哈，被發現了。. 其實我之前還想到一個變形，就是給定常數個排序陣列找第 k 位。. 如果套用行排序的方法，會需要O(lg^2 n)。. 但是我們知道兩個陣列找中位數只需要O(lg n)的時間。. 不過如果用我之前說的方法，找中位數就只需要O(lg n)的時間了。. 那篇paper是講行列排序時O(n
(還有61個字)
內容預覽:
FRAXIS 這是你的文章嗎？. http://algnotes.wordpress.com/2014/10/09/. 看完這個我就想通了. 行列已排序的陣列，可以用階梯狀移動的方法找rank（做partition），O(n). 只有行排序的陣列，可以用 n 次 binary search 找 ra
(還有500個字)
內容預覽:
其實把DWJS的方法稍微改一下就可以了。. 對於目前的n條序各列改中位數 O(1). n個中位數找中位數(MoM) O(n). 對每一條序列用binary search找比MoM大和小各有多少個 O(n logn). 會有 n_l個比MoM小，n_r個比MoM大，選擇目標的那一邊。. 更新序列的 h
(還有285個字)
內容預覽:
對於這裡我有點困惑. 若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個字)
內容預覽:
昨天睡覺時用力想了一陣. 事實上不需要跑 binary search，也不必跑 partition. 這邊重新整理一下. 給定 n 個長度 n 已排序陣列，找第 k 小的元素. 每個陣列都有兩個指標 low = 0 和 high = n-1 O(n). 每個陣列的大小 size = high - l
(還有861個字)