有一个大小为n的数组(数字介于0和n - 3之间),只重复2个数字.元素随机放置在数组中.
例如,在{2,3,6,1,5,4,0,3,5} n = 9,重复数为3和5.
找到重复数字的最佳方法是什么？
PS [你不应该使用排序]
请仔细阅读此问题,然后将其作为副本关闭,但如果它是一个诚实的副本,我将很高兴知道它.这是查找列表中多个可能的重复整数中的任何一个的概括.
给定任意一组小号的Ñ不同的整数,任何阵列甲的长度N + 1,其中每个条目取自小号,什么是找到一些(必须有至少一个)重复条目的最佳算法甲？
注意:A中可能有多个重复条目,任何条目都可以重复多次.
正如Nemo指出的那样,平凡的解决方案需要O(1)空间和O(N ^ 2)时间.我正在寻找一种能够在不影响空间的情况下缩短时间的解决方案.确切地说,我正在寻找的解决方案:
编辑:集合S用于确保阵列A至少有一个重复的条目.对于这个问题,不要假设您已将S作为有序集给出.您可以查询小号(布尔返回true是S IN小号和false其他),你可以查询一个(请致电A [1] ),但仅此而已.任何对A或S进行排序的解决方案都超出了空间限制.
这种推广使我对原始问题(具有O(1)空间和O(N)时间)的指针解决方案 …
给定N个整数的数组,使得只重复一个整数.在O(n)时间和常量空间中找到重复的整数.整数值或N的值没有范围
例如,给出一个由6个整数组成的数组,如23 45 67 87 23 47.答案是23(我希望这涵盖模糊和含糊的部分)
我在网上搜索但无法找到任何这样的问题,其中整数范围没有固定.还这里是,回答一个类似的问题,以矿一个例子,但在这里,他创建的哈希表C++中的最高整数值,但CPP不允许这样的64位的计算机上创建与2 ^ 64元件(阵列).
对不起,在数组不可变之前我没有提到它
问题:给出一系列从1到n-1的数字,其中一个数字只重复一次.(例如:1 2 3 3 4 5).你怎么能找到重复的数字？
通常,对这个问题的所谓"聪明"回答是将其总结并找出与预期总和的差异.但为什么不只是走过清单并检查之前的数字呢？两者都是O(n).我错过了什么吗？