[問題] 第 k 大連續子陣列和
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間9年前 (2015/02/27 22:39)推噓2(2推 0噓 9→)留言11則, 3人參與討論串1/5 (看更多)
這算是經典的最大連續子陣列和的變形吧。
給定一個長度為 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://www.ptt.cc/bbs/Prob_Solve/M.1425047953.A.AAD.html
※ 編輯: FRAXIS (129.170.195.149), 02/27/2015 22:40:17
推
02/27 23:16, , 1F
02/27 23:16, 1F
→
02/27 23:18, , 2F
02/27 23:18, 2F
→
02/27 23:18, , 3F
02/27 23:18, 3F
→
02/28 02:07, , 4F
02/28 02:07, 4F
→
02/28 02:21, , 5F
02/28 02:21, 5F
→
02/28 02:22, , 6F
02/28 02:22, 6F
→
02/28 02:23, , 7F
02/28 02:23, 7F
→
02/28 02:23, , 8F
02/28 02:23, 8F
→
02/28 02:25, , 9F
02/28 02:25, 9F
推
02/28 07:08, , 10F
02/28 07:08, 10F
→
02/28 07:09, , 11F
02/28 07:09, 11F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-4
30