作者penknifelee (狂禪)
看板Prob_Solve
標題[問題] 一串數字中找到相同的兩個數
時間Mon Dec 1 21:25:44 2014
問題：
給定n個數(不限整數或浮點數，也不限上下界)，
如果已知其中僅有兩個數相等，
要如何找到這兩個數呢？
我只想得到先sort後再找，
但這樣感覺多做了很多事情，
請問有沒有低於O(nlogn)、最好是O(n)的做法呢？
感謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.91.142
※ 文章網址: http://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1417440347.A.3F4.html
1F：推 fenzhang: hash_set 12/01 21:42
2F：→ freef1y3: 一個一個丟進binary search tree，丟之前先檢查是不是 12/01 23:08
3F：→ freef1y3: 已經在tree裡了 12/01 23:08
4F：推 Elohim123: 用BST的話應該也是O(nlogn)? 因為每次丟數字進去的時候 12/02 23:39
5F：→ Elohim123: 也花了logn 12/02 23:39
6F：→ penknifelee: 我的想法與樓上相同 另外可否請一樓做進一步的解說？ 12/03 16:26
7F：推 CaptainH: 把浮點數表示法視為整數，然後用xor找？ 12/04 03:15
8F：推 LPH66: 我的感覺是如果只准比較那好像逃不出 O(nlogn) 12/04 14:54
9F：→ LPH66: 不過暫時還沒有證明就是了... 12/04 14:55
10F：推 pika0923: 使用資料表達的bit來作BST的話 運算數正比於樹走訪深度 12/07 11:47
11F：→ pika0923: 而樹的深度正比於資料大小 ->O(n) 12/07 11:47
12F：→ pika0923: 兩篇前的perfect hashing那邊我有寫一個類似的作法 12/07 11:50
13F：→ pigalan: 樓上這樣是O(nlogC)吧, C是數值大小 12/09 02:16
14F：推 pika0923: 其實n原本就是input size而不是package size 12/09 12:26
15F：→ pika0923: 看總bit數在armotize後不會發生算了n又要算logC的狀況 12/09 12:27
16F：→ pika0923: 例:讀入任意數量的任意長度整數是O(n) 12/09 12:30
17F：→ penknifelee: 真厲害，感謝！ 12/17 18:48