[问题] 一串数字中找到相同的两个数 penknifelee PTT批踢踢实业坊

楼主: penknifelee (狂禅) 2014-12-01 21:25:44

问题：
给定n个数(不限整数或浮点数，也不限上下界)，
如果已知其中仅有两个数相等，
要如何找到这两个数呢？
我只想得到先sort后再找，
但这样感觉多做了很多事情，
请问有没有低于O(nlogn)、最好是O(n)的做法呢？
感谢！

作者: fenzhang (分帐) 2014-12-01 21:42:00

hash_set

作者: freef1y3 ( ) 2014-12-01 23:08:00

一个一个丢进binary search tree，丢之前先检查是不是已经在tree里了

作者: Elohim123 (全力以赴) 2014-12-02 23:39:00

用BST的话应该也是O(nlogn)? 因为每次丢数字进去的时候也花了logn

楼主: penknifelee (狂禅) 2014-12-03 16:26:00

我的想法与楼上相同另外可否请一楼做进一步的解说？

作者: CaptainH (Cannon) 2014-12-04 03:15:00

把浮点数表示法视为整数，然后用xor找？

作者: LPH66 (-6.2598534e+18f) 2014-12-04 14:54:00

我的感觉是如果只准比较那好像逃不出 O(nlogn)不过暂时还没有证明就是了...

作者: pika0923 (宜安) 2014-12-07 11:47:00

使用资料表达的bit来作BST的话运算数正比于树走访深度而树的深度正比于资料大小 ->O(n)两篇前的perfect hashing那边我有写一个类似的作法

作者: pigalan (Tomato) 2014-12-09 02:16:00

楼上这样是O(nlogC)吧, C是数值大小

作者: pika0923 (宜安) 2014-12-09 12:26:00

其实n原本就是input size而不是package size看总bit数在armotize后不会发生算了n又要算logC的状况例:读入任意数量的任意长度整数是O(n)

楼主: penknifelee (狂禅) 2014-12-17 18:48:00

真厉害，感谢！

继续阅读