PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 第 k 大連續子陣列和

看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間9年前 (2015/02/28 07:26)推噓1(1推 0噓 2→)

留言3則, 2人參與討論串2/5 (看更多)

※ 引述《FRAXIS (喔喔)》之銘言： : 這算是經典的最大連續子陣列和的變形吧。 : 給定一個長度為 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 最近剛好有遇到類似的問題我想你問的應該是靜態問題而不是動態問題吧？令 sum[i][j] = a[i] + ... + a[j] 是連續和把 sum 畫成一個矩陣只有上三角，對角線是 a[0] 到 a[n-1] 整個結構類似 pascal 三角形，不過這裡是越右上越大，右上角是總和 a[0] + ... + a[n-1] 目標是從上三角當中找到第k大之前在這個板有討論過一個類似的問題：已排序陣列找第k大、row已排序陣列找第k大 ┌─────────────────────────────────────┐ │ 文章代碼(AID): #1KF5PfAs (Prob_Solve) [ptt.cc] [問題] 給定n個排好序的整? │ │ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1413240425.A.2B6.html │ │ 這一篇文章值 107 Ptt幣 │ └─────────────────────────────────────┘ 應該就是這樣解吧？只不過這個問題的陣列元素不是已知所以要先算個前綴和，就能以O(1)時間求得陣列元素 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.79.38 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1425079575.A.53B.html ※ 編輯: DJWS (111.250.79.38), 02/28/2015 07:34:55 ※ 編輯: DJWS (111.250.79.38), 02/28/2015 07:46:31