Re: [問題] 第 k 大連續子陣列和
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間9年前 (2015/02/28 08:06)推噓1(1推 0噓 3→)留言4則, 2人參與討論串3/5 (看更多)
推
02/27 23:16,
02/27 23:16
→
02/27 23:18,
02/27 23:18
→
02/27 23:18,
02/27 23:18
→
02/28 02:07,
02/28 02:07
→
02/28 02:21,
02/28 02:21
說到 RANGE
最近剛好有學到一個 fourier transform 的方法 分享一下
時間複雜度是 O(n + RANGE log RANGE)
首先計算前綴和 prefix_sum(x) = a[0] + ... + a[x]
連續和就是 prefix_sum(j) - prefix_sum(i-1) 兩數相減的形式
這個東西可以套用 pairwise sum problem
http://en.wikipedia.org/wiki/Pairwise_summation
把第二個陣列頭尾顛倒一下，另外扣個常數，就是兩數相減的形式了
演算法大概是這樣：
1. 先用 O(n) 算前綴和
2. 再用 O(n + RANGE) 從循序儲存，換成索引儲存(counting sort那樣子)
3. 跑個 fourier transform 換到頻域去算，再換回來，總共 O(RANGE log RANGE)
然後這個板之前有個問題也可以這樣解
┌─────────────────────────────────────┐
│ 文章代碼(AID): #1FP0xbjA (Prob_Solve) [ptt.cc] [問題] 貌似Facebook面試題 │
│ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1331957477.A.B4A.html │
│ 這一篇文章值 39 Ptt幣 │
└─────────────────────────────────────┘
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.79.38
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1425082011.A.50E.html
※ 編輯: DJWS (111.250.79.38), 02/28/2015 08:08:45
※ 編輯: DJWS (111.250.79.38), 02/28/2015 08:09:21
推
03/02 00:09, , 1F
03/02 00:09, 1F
→
03/02 08:07, , 2F
03/02 08:07, 2F
→
03/02 08:08, , 3F
03/02 08:08, 3F
→
03/02 08:09, , 4F
03/02 08:09, 4F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-4
30