问题：
给定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)

真厉害，感谢！