问题描述：有一组数字，从1到n，从中减少了3个数，顺序也被打乱，放在一个n-3的数组里

请找出丢失的数字，最好能有程序，最好算法比较快
假设n=10000

我的解题思路：

我用bitmap法实现的。思路如下：
一个[1，m]的bitmap（求简单，每个元素都是bool类型），全部初始化为false。
第一步
便利目标数组，用每一个值作下表，找到bitmap中对应位置，置true。
第二部：
扫描bitmap中为true的节点，记录下来，这就是答案
只需要便利两次数组即可。

c代码如下：

关键解题函数：

void FindLostNum(int* pData, int nTotalNum, int* pResult, int nLost)
参数解释： pData 指向一个整型数组,里面有nTotalNum个乱序数据元素，元素取值[1,nTotalNum+nLost] pResult 指向一个结果整型数组，里面有nLost个节点，用来接收返回结果代码在vs2010下调试通过

#include
#include
using namespace std;

#define N (4000)
#define LOST (3)

typedef struct _NODE_NUM
{
bool bUsed; //是否被用过
}NODE_NUM, *PNODE_NUM;

//生成数表，[1,n]乱序。 参数：表头指针，总数，丢失的个数
bool GenerateRandomNumSet(PNODE_NUM pData, int nTotalNum, int nLostNum);

//找出丢失的数字
void FindLostNum(int* pData, int nTotalNum, int* pResult, int nLost);

bool GenerateRandomNumSet(int* pData, int nTotalNum, int nLostNum)
{
PNODE_NUM pList = NULL;
int index = 0;
int temp = 0;
int loc = 0;

if(pData==NULL || nTotalNum<=0)
return false;

//初始化1-n数码顺序表
pList = new NODE_NUM[nTotalNum];
if(pList == NULL)
return false;
for(index=0; index {
(pList+index)->bUsed = false;
}

/*初始化[1，n-lost]乱序数码表*/
try
{
for(index=0; index {

loc = rand()%nTotalNum;
while(1)
{
if((pList+loc)->bUsed)
{
loc++;
if(loc >= nTotalNum)
loc=0;
}
else
break;
}
*(pData+index) = loc;
(pList+loc)->bUsed = true;
}
}
catch(exception e)
{
cout<<"参数错误";
}

delete pList;
return true;
}

void FindLostNum(int* pData, int nTotalNum, int* pResult, int nLost)
{
PNODE_NUM pList = NULL;
int index=0;
int count = 0;

if(pData==NULL || nTotalNum<=0 || pResult==NULL || nLost<=0)
return;

//初始化1-n数码顺序表
pList = new NODE_NUM[nTotalNum+nLost];
if(pList == NULL)
return;
for(index=0; index {
(pList+index)->bUsed = false;
}

//扫描给出数列，在pList中标记
for(index=0; index {
(pList+*(pData+index))->bUsed =true;
}

for(index=0; index {
if(!(pList+index)->bUsed)
{
*(pResult+count) = index;
count++;
}
}
}
int main()
{
int* pData = NULL;
int* pResult = NULL;

pData = new int[N];
if(pData==NULL)
return -1;

pResult = new int[LOST];
if(pResult==NULL)
{
delete pData;
return -1;
}

GenerateRandomNumSet(pData, N, LOST);

FindLostNum(pData, N-LOST, pResult, LOST);

//输出结果
for(int index=0; index cout<<*(pResult+index)<<"\t";

//检验结果
for(int index=0; index {
for(int c=0; c {
if(*(pData+index) == *(pResult+c))
cout< }
}

delete pData;
delete pResult;
return 1;
}