作者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