在唯一编号数组中寻找重复的数字

有一个数组除了一个数字（比如magic-number）都是唯一的。神奇数字重复自己超过数组大小的一半。例如2，10，10，10，3.使用任何额外空间并且不对其进行排序，找到没有的幻数。现在有什么方法可以在O（n）中完成它。在唯一编号数组中寻找重复的数字

2016-07-20 Alex_ban

“没有使用任何额外的空间”，你的意思是说你不能分配另一个搜索到的数字列表？基本上，只有列表的指针/索引是有效的？ – user1676075

当然你总是需要指针和索引 –

检查每个元素对其邻居，如果任何相等，那么你已经找到了数字。 O（N）

如果第一次测试没有发现号码，然后你在以下情况：

10,2,10,3,10.

在这种情况下，数组中的第一个数字是一个神奇的数字。 O（1）

2016-07-20 16:16:21

回答