给定的阵列n+1整数,每个范围1来n,发现反复的整数.
在面试时我被问到这个问题.这是我的答案:鸽笼原则说必须重复一遍.我尝试使用二进制搜索方法,所以我在Matlab中做了这个,因为这就是我所知道的:
top = 0;
bot = 0;
for i=1:n+1
if P[i] > n/2
top = top+1;
else
bot = bot+1;
end
所以我认为其中一个,top或者bot,必须比n/2PhP 更大.取这个范围并重复.
我认为这是一个非常好的解决方案,但面试官有点暗示一个人可以做得更好.请发布您知道的更好的解决方案.
给定N个整数的数组,使得只重复一个整数.在O(n)时间和常量空间中找到重复的整数.整数值或N的值没有范围
例如,给出一个由6个整数组成的数组,如23 45 67 87 23 47.答案是23(我希望这涵盖模糊和含糊的部分)
我在网上搜索但无法找到任何这样的问题,其中整数范围没有固定.还这里是,回答一个类似的问题,以矿一个例子,但在这里,他创建的哈希表C++中的最高整数值,但CPP不允许这样的64位的计算机上创建与2 ^ 64元件(阵列).
对不起,在数组不可变之前我没有提到它