[腾讯面试]有1到10w这10w个数,去除2个并打乱次序,如何找出那两个数

时间:2022-05-30 11:08:26

描述:有1到10w这10w个数,去除2个并打乱次序,如何找出那两个数。(不准用位图!!)
位图解决:

位图的方法如下
假设待处理数组为A[10w-2]
定义一个数组B[10w],这里假设B中每个元素占用1比特,并初始化为全0
for(i=0;i <10w-2;i++)
{
 B[ A[i] ]=1
}
那么B中为零的元素即为缺少的数据
这种方法的效率非常高,是计算机中最常用的算法之一
其它方法:
      求和以及平方和可以得到结果,不过可能求平方和运算量比较大(用64位int不会溢出)