算法找到在不断的空间和O（n）时间重复项 [英] Algorithm to find a duplicate entry in constant space and O(n) time

问题描述

给定N整数的阵列使得只有一个整数是重复的。查找在O（n）的时间和空间，不断重复的整数。有没有范围的整数的值或N值

Given an array of N integer such that only one integer is repeated. Find the repeated integer in O(n) time and constant space. There is no range for the value of integers or the value of N

例如给予6的整数数组为23 45 67 87 23 47。答案是23 （我希望这包括含糊不清的部分）

For example given an array of 6 integers as 23 45 67 87 23 47. The answer is 23 (I hope this covers ambiguous and vague part)

我在网上搜索，但未能找到其整数范围为不固定的任何问题。 此外这里是回答了类似的问题，以我的一个例子，但在这里，他创建了在C ++中的最高整数值的哈希表，但CPP不允许这样来创建2 ^ 64元素的数组（64位计算机上）。

I searched on the net but was unable to find any such question in which range of integers was not fixed. Also here is an example that answers a similar question to mine but here he created a hash table with the highest integer value in C++.But the cpp does not allow such to create an array with 2^64 element(on a 64-bit computer).

我很抱歉，我没有提到它前阵是不可改变的。

I am sorry I didn't mention it before the array is immutable

推荐答案

如果阵列没有排序，你只能做它 O（nlogn）。

If the array isn't sorted, you can only do it in O(nlogn).

一些方法可以发现这里 。

Some approaches can be found here.

这篇关于算法找到在不断的空间和O（n）时间重复项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！