[問題] 一串數字中找到相同的兩個數

[penknifelee (狂禪)]

問題：

給定n個數(不限整數或浮點數，也不限上下界)，

如果已知其中僅有兩個數相等，

要如何找到這兩個數呢？


我只想得到先sort後再找，

但這樣感覺多做了很多事情，

請問有沒有低於O(nlogn)、最好是O(n)的做法呢？

感謝！

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.91.142
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1417440347.A.3F4.html
推 fenzhang: hash_set
→ freef1y3: 一個一個丟進binary search tree，丟之前先檢查是不是
→ freef1y3: 已經在tree裡了
推 Elohim123: 用BST的話應該也是O(nlogn)? 因為每次丟數字進去的時候
→ Elohim123: 也花了logn
→ penknifelee: 我的想法與樓上相同 另外可否請一樓做進一步的解說？
推 CaptainH: 把浮點數表示法視為整數，然後用xor找？
推 LPH66: 我的感覺是如果只准比較那好像逃不出 O(nlogn)
→ LPH66: 不過暫時還沒有證明就是了...
推 pika0923: 使用資料表達的bit來作BST的話 運算數正比於樹走訪深度
→ pika0923: 而樹的深度正比於資料大小 ->O(n)
→ pika0923: 兩篇前的perfect hashing那邊我有寫一個類似的作法
→ pigalan: 樓上這樣是O(nlogC)吧, C是數值大小
推 pika0923: 其實n原本就是input size而不是package size
→ pika0923: 看總bit數在armotize後不會發生算了n又要算logC的狀況
→ pika0923: 例:讀入任意數量的任意長度整數是O(n)
→ penknifelee: 真厲害，感謝！