面试题实现--（百度的不存在数查找问题）

百度最新面试题：现在有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来。

这种类似的题很多，今天之所以写出来，主要是实际体验一下这么多数据的情况下，到底速度怎么样。如果不考虑空间，其实最简单的就是利用计数排序的方法进行，时间复杂度为N+M.下面是我的实现：

private const uint Nums = 10000000;
private const uint MaxNum = 100000000;
private void button2_Click(object sender, EventArgs e)
{
//保存32位基数1,2,4,8,16.....，不必每次都进行位移.
UInt32[] theBases = new UInt32[32];
UInt32 theDigit = 1;
for(int i=0;i<32;i++)
{
theBases[i] = theDigit;
theDigit = theDigit << 1;
}
TimeSpan theTS1 = new TimeSpan(DateTime.Now.Ticks);
//读取文件，二进制比文本格式要快很多，而且空间需求也小。
System.IO.FileStream theFS = new System.IO.FileStream("D:\\tempnum.txt", System.IO.FileMode.Open, System.IO.FileAccess.Read);
System.IO.StreamReader theBR = new System.IO.StreamReader(theFS);
UInt32 theNum, theTmp;
UInt32 theIndex = 0;
//计算总共需要的数组空间，因为每个无符号整数代表32个数，则总共需要N/32+1个无符号整数.
UInt32 theArrayTop = (MaxNum >> 5) + 1;
UInt32[] theNumbers = new UInt32[theArrayTop];
UInt32 iPos = 0;
try
{
//读文件，直到结束.
while (theBR.EndOfStream==false)
{
theNum = uint.Parse(theBR.ReadLine());
iPos = (theNum - 1) & (uint)31;//计算在一个表示整数中的位置。
theIndex = (theNum - 1) >> 5;//计算在第几个无符号整数，数组下标.
theTmp = theNumbers[theIndex];//获取theIndex指向的无符号整数.
theTmp = theTmp | theBases[iPos];//设置当前表示位置为1，存在.
theNumbers[theIndex] = theTmp;
}
}
catch
{
}
finally
{
theBR.Close();
theFS.Close();
theFS.Dispose();
}
//遍历，并把不存在的数写入文件.
System.IO.FileStream theFS1 = new System.IO.FileStream("D:\\tempnum1.txt", System.IO.FileMode.CreateNew, System.IO.FileAccess.Write);
System.IO.StreamWriter bw1 = new System.IO.StreamWriter(theFS1);
for (UInt32 i = 0; i < MaxNum; i++)
{
//计算当前整数所在整数和整数中的位置.
iPos = i & 31;//(===i%32)
theIndex = i >> 5;//(=== i / 32 整除)
theNum = theNumbers[theIndex];
//测试代表位如果为0，表示不存在，则输出.
if ((theNum & theBases[iPos]) == 0)
{
bw1.WriteLine(i + 1);
}
}
bw1.Flush();
bw1.Close();
theFS1.Close();
theFS1.Dispose();
TimeSpan theTS2 = new TimeSpan(DateTime.Now.Ticks);
this.textBox1.Text = theTS2.Subtract(theTS1).Seconds.ToString();
}

我用二进制输入和输出，对于1亿个随机数的情况下在我的机器上花费的时间是26秒，用文本输入和输出，1千万随机数用了接近1分钟。