如何识别数组中具有最小紧度的重复数字？
如何识别数组中具有最小紧度的重复数字？
提问于 2011-04-23 05:12:48
有一个大小为10,000的数组。它按随机顺序存储数字1到10,000。
每个数字只发生一次。
现在，如果从该数组中删除任何数字，并且将任何其他数字复制到数组中。
我们如何识别哪个数字是重复的，以最小的复杂度？
注意:我们不能使用其他数组。
回答 3
Stack Overflow用户
回答已采纳
发布于 2011-04-23 05:36:42
最快的方法是O(N)就地鸽子孔排序.
从数组的第一个位置a[0]开始。假设它的值为5。您知道5属于a[4]，所以交换位置0和4。现在，在a[0]中有一个新的值。换到它该去的地方。
重复到a[0] == 1，然后转到a[1]，交换到a[1] == 2等等。
如果您在任何时候都试图交换两个相同的值，那么您已经找到了副本！
运行时: O(N)具有非常低的系数和早期退出。存储要求:零。
额外优化:计算发生了多少次掉期，如果n_swaps == array_size提前退出。当我实现a similar algorithm来配置一个序列时，这导致了15%的改进。
Stack Overflow用户
发布于 2011-04-23 05:34:02
为什么不简单地使用第二个数组或其他数据结构，如哈希表(哈希表，如果您愿意，取决于内存/性能权衡)。第二个数组将简单地将一个数字的计数存储在原始数组中。现在，只需将+/-添加到原始数组的访问函数中，您就可以立即获得信息。
ps当你写“我们不能使用另一个数组”--我想，你不能改变原始的数据结构。然而，可以使用额外的数据结构。
Stack Overflow用户
发布于 2011-04-23 05:46:34
对数组进行排序，然后迭代，直到在一行中找到两个相同的数字。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5762334
复制相关文章
相似问题
腾讯云开发者
