高考问答玩老虎机输得一无所有:微软面试题
来源：百度文库 编辑：高考问答 时间：2024/05/06 11:10:59
有一个用1001个整数组成的数组，这些整数任意排列并都在1到1000（包括1000）之间。除一个数字出现两次外，其他所有数字只出现一次。只对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗？
我觉得要用桶排序,时间复杂度高一些,首先是定义一个数组a[1001]; 把相应的数字插入到对应的地址空间里去,例如原始数据放在 data[1001]中
for(int i=0;i<1001;i++)
if (a[data[i]] != data[i])
a[data[i]] = data[i];
else
printf("the repeated is %d", data[i]);
不用辅助数组的话,我觉得排序一次,在相临比较一次.不知道对不对
将这1001个数相加,再减去1到1000的数的和,所得的即为重复的数字(注意到除一个数字出现两次外，其他所有数字只出现一次,那么1到1000的数都出现了)
不会这么简单吧??呵呵