作者FRAXIS (喔喔)
看板Prob_Solve
標題[問題] 第 k 大連續子陣列和
時間Fri Feb 27 22:39:11 2015
這算是經典的最大連續子陣列和的變形吧。
給定一個長度為 n 的整數陣列，和一個正整數 k 。
找出一個在所有 C(n, 2) 個連續子陣列中，總和第 k 大的連續子陣列。
理論上是可以做到 O(n)，但是這方法應該不實用。
雖然也有其他的O(n lg n)，O(n lg^2 n)和O(n lg^3 n)的方法，
但是好像都不太實際 （O(n lg^3 n)的方法或許比較可行..）
我的問題是： 有沒有實際上比較有效率（o(n^2)）且好實作的方法呢？
這問題是在 careercup 上看到的面試問題
http://www.careercup.com/question?id=12804676
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.149
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1425047953.A.AAD.html
※ 編輯: FRAXIS (129.170.195.149), 02/27/2015 22:40:17
1F：推 suhorng: 對答案二分搜 02/27 23:16
2F：→ suhorng: O(n log n log RANGE), 不能說是 o(n^2) 就是... 02/27 23:18
4F：→ suhorng: ^^^^^ 這邊不確定一個 log 還兩個 log 02/28 02:07
5F：→ FRAXIS: 應該是一個log 沒錯 02/28 02:21
6F：→ FRAXIS: 而且這方法也可以解決 找出長度在l~u之間的第 k 大連續和 02/28 02:22
7F：→ FRAXIS: 不過如果題目是找第 k 大 density 連續子陣列 02/28 02:23
8F：→ FRAXIS: 有沒有類似的技巧可以使用呢？ 02/28 02:23
9F：→ FRAXIS: density 我是指 average := 總和 / 長度 02/28 02:25
10F：推 DJWS: 1.算前綴和 2.窮舉所有連續和/平均 3.找第k大是線性時間 02/28 07:08
11F：→ DJWS: 抱歉 我看到那是小寫了... 02/28 07:09