作者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/cn.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