Re: [問題] 第 k 大連續子陣列和
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間9年前 (2015/02/28 22:29)推噓0(0推 0噓 0→)留言0則, 0人參與討論串4/5 (看更多)
: ※ 引述《FRAXIS (喔喔)》之銘言：
: 令 sum[i][j] = a[i] + ... + a[j] 是連續和
: 把 sum 畫成一個矩陣
: 只有上三角，對角線是 a[0] 到 a[n-1]
: 目標是從上三角當中找到第k大
: 應該就是這樣解吧？
: 只不過這個問題的陣列元素不是已知
: 所以要先算個前綴和，就能以O(1)時間求得陣列元素
我也有想過這樣作，這樣就可以擺脫掉 range。
令P[i] = A[1..i], P[0] = 0
SUM[i][j] = 結尾在 i 第 j 大的連續和
= P[i] - (P[0] ~ P[i-1] 中第 j 小數)
給定 (i, j) 利用 range median query 可以在O(lg n)時間內算出 SUM[i][j]
每一直列都是有序的，然後用 selection in sorted arrays 找出第 k 大元素。
時間複雜度會是O(n lg n) ~ O(n lg^3 n)
取決於 selection in sorted arrays 的效率。
不過這方法沒辦法解決 第 k 大 maximum density segment 問題。
我想到的方法都是基於 Theil-Sen estimator 的方法。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.149
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1425133750.A.37A.html
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-4
30