Re: [問題] 數列中找出某兩數之和等於數列中另一數
看板Prob_Solve (計算數學 Problem Solving)作者LPH66 ((short)(-15074))時間16年前 (2008/10/30 09:36)推噓2(2推 0噓 1→)留言3則, 3人參與討論串2/2 (看更多)
※ 引述《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
推
11/01 23:52, , 1F
11/01 23:52, 1F
推
11/02 18:48, , 2F
11/02 18:48, 2F
→
11/03 00:12, , 3F
11/03 00:12, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
