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