作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 第 k 大连续子阵列和
时间Sat Feb 28 08:06:47 2015
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
说到 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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1331957477.A.B4A.html │
│ 这一篇文章值 39 Ptt币 │
└─────────────────────────────────────┘
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.250.79.38
※ 文章网址: https://webptt.com/cn.aspx?n=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
6F：推 FRAXIS: 还有没有什麽其他问题可以应用这技巧的？ 03/02 00:09
8F：→ DJWS: 然後算法竞赛有一些相关题目 用关键字FFT去找可以找到一些 03/02 08:08
9F：→ DJWS: 其他的我就不知道了 我没有追踪论文 03/02 08:09