問題：
給定n個數(不限整數或浮點數，也不限上下界)，
如果已知其中僅有兩個數相等，
要如何找到這兩個數呢？
我只想得到先sort後再找，
但這樣感覺多做了很多事情，
請問有沒有低於O(nlogn)、最好是O(n)的做法呢？
感謝！

hash_set

一個一個丟進binary search tree，丟之前先檢查是不是已經在tree裡了

用BST的話應該也是O(nlogn)? 因為每次丟數字進去的時候也花了logn

我的想法與樓上相同 另外可否請一樓做進一步的解說？

把浮點數表示法視為整數，然後用xor找？

我的感覺是如果只准比較那好像逃不出 O(nlogn)不過暫時還沒有證明就是了...

使用資料表達的bit來作BST的話 運算數正比於樹走訪深度而樹的深度正比於資料大小 ->O(n)兩篇前的perfect hashing那邊我有寫一個類似的作法

樓上這樣是O(nlogC)吧, C是數值大小

其實n原本就是input size而不是package size看總bit數在armotize後不會發生算了n又要算logC的狀況例:讀入任意數量的任意長度整數是O(n)

真厲害，感謝！