给定N个整数的数组,使得只重复一个整数.在O(n)时间和常量空间中找到重复的整数.整数值或N的值没有范围
例如,给出一个由6个整数组成的数组,如23 45 67 87 23 47.答案是23(我希望这涵盖模糊和含糊的部分)
我在网上搜索但无法找到任何这样的问题,其中整数范围没有固定.还这里是,回答一个类似的问题,以矿一个例子,但在这里,他创建的哈希表C++中的最高整数值,但CPP不允许这样的64位的计算机上创建与2 ^ 64元件(阵列).
对不起,在数组不可变之前我没有提到它
Jun Tarui已经证明,任何使用O(log n)空间的重复查找器都需要至少Ω(log n/log log n)通过,这超过了线性时间.即使你允许对数空间,你的问题也证明是无法解决的.
Gopalan和Radhakrishnan 有一个有趣的算法,它在输入和O((log n)^ 3)空间的一次传递中找到重复的算法,这听起来像是你事先做的最好的选择.
基数排序具有时间复杂度O(kn),其中k> log_2 n经常被视为常数,尽管是大常数.您无法在常量空间中实现基数排序,但您可以重用输入数据的空间.
如果你假设数字本身的特征,有一些数字技巧.如果几乎存在1和n之间的所有数字,则只需将它们相加并减去n(n + 1)/ 2.如果所有数字都是素数,你可以通过忽略除法的运行时间来作弊.
另外,在比较排序中有一个众所周知的Ω下限(log_2(n!)),这表明谷歌可能会帮助您找到简单问题的下限,例如查找重复项.
| 归档时间： |
|
| 查看次数： |
4865 次 |
| 最近记录： |