相关疑难解决方法(0)

有一个大小为n的数组(数字介于0和n - 3之间),只重复2个数字.元素随机放置在数组中.

例如,在{2,3,6,1,5,4,0,3,5} n = 9,重复数为3和5.

找到重复数字的最佳方法是什么？

PS [你不应该使用排序]

给定的阵列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 更大.取这个范围并重复.

我认为这是一个非常好的解决方案,但面试官有点暗示一个人可以做得更好.请发布您知道的更好的解决方案.