我们怎样才能找到一个重复号码阵列中的O（n）时间及O（1）空间复杂度 [英] How can we find a repeated number in array in O(n) time and O(1) space complexity

问题描述

如何才能找到在阵列中的O（n）时间及O（1）复杂性，重复的次数？ 例如 阵列2,1,4,3,3,10 输出3

How can we find a repeated number in array in O(n) time and O(1) complexity? eg array 2,1,4,3,3,10 output is 3

编辑： 我试着在下面的方式。 我发现，如果没有被奇怪地重复，然后我们就可以实现的结果做异。所以我想使这是奇怪的没有重复的元素，甚至没有一位均匀地重复没有要odd.but的，我需要找出从输入数组的独特元素的数组中为O（n），但找不到办法​​。

I tried in following way. i found that if no is oddly repeated then we can achieve the result by doing xor . so i thought to make the element which is odd no repeating to even no and every evenly repeating no to odd.but for that i need to find out unique element array from input array in O(n) but couldn't find the way.

推荐答案

假设有一个调升开往号的数组中的值（也就是在所有的编程语言都内建整数类型的情况下，我'已经使用过 - 例如，让我们说，他们是32位整数），有一个解决方案，使用恒定的空间：

Assuming that there is an upped bound for the values of the numbers in the array (which is the case with all built-in integer types in all programming languages I 've ever used -- for example, let's say they are 32-bit integers) there is a solution that uses constant space:

1. 创建N个元素，其中N为上限输入数组中的整数值的数组，并初始化所有元素 0 或假或某些等效。我会称之为查找的数组。
2. 遍历输入数组，并使用每个号码来索引到查找阵列。如果您发现该值为 1 或真（等），输入数组中的当前号码是重复的。
3. 否则，查找数组中的相应值设置为 1 或真要记住，我们已经看到了这一点特别是输入数字。

1. Create an array of N elements, where N is the upper bound for the integer values in the input array and initialize all elements to 0 or false or some equivalent. I 'll call this the lookup array.
2. Loop over the input array, and use each number to index into the lookup array. If the value you find is 1 or true (etc), the current number in the input array is a duplicate.
3. Otherwise, set the corresponding value in the lookup array to 1 or true to remember that we have seen this particular input number.

技术上的，这是O（n）时间及O（1）空间，而且不破坏输入数组。实际上，你需要的东西是会用自己的方式有这样的程序实际运行（例如，它是不可能的，如果谈到64位整数输入）。

Technically, this is O(n) time and O(1) space, and it does not destroy the input array. Practically, you would need things to be going your way to have such a program actually run (e.g. it's out of the question if talking about 64-bit integers in the input).

这篇关于我们怎样才能找到一个重复号码阵列中的O（n）时间及O（1）空间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！