作者LPH66 ((short)(-15074))
看板Prob_Solve
标题Re: [问题] 数列中找出某两数之和等於数列中另一数
时间Thu Oct 30 09:36:25 2008
※ 引述《willhunting (这些年来)》之铭言：
: 如题，请问这样的问题有O(N*logN)的解法吗?谢谢各位
在限定所有数字是整数 而且题目只问有没有的条件下
我是凑出了一个O(N+RlogR)的解法 其中R是数字的范围
方法如下:
令数列中最小值为m 即最大值为m+R
首先, 用O(N)的时间把这组N个资料转换成一个R次多项式 f(x)
其中x^k项系数表示这N个资料中k+m有几个
再来 利用一个有点恶心的O(RlogR)的多项式乘法演算法
(详情可见Introduction to Algorithm Chap.30 利用到离散傅立叶转换)
计算g(x) = [f(x)]^2 = f(x) * f(x)
然後将g(x)的x^(-m)到x^(-m+R)项的系数和f(x)的x^0到x^R系数比较
只要两边某一项系数都非0就是找到有了 这需要O(R)
总共加起来就是O(N+RlogR)
--
有人喜欢边
玩游戏边
上逼；
也有人喜欢边
听歌边
打字。
但是，我有个请求，
选字的时候请
专心好吗？
-- 改编自「古 火田 任三郎」之开场白
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.84
1F：推 willhunting:真是前所未闻的高超解法 感谢! 11/01 23:52
2F：推 FRAXIS:很有创意的方法 不过R有可能比n要来的大.. 11/02 18:48
3F：→ LPH66:嗯, 所以我不敢说这就是原PO要的nlogn解法 11/03 00:12