解一道面试题

问题描述：有一组数字，从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 <iostream> 
#include <math.h> 
using namespace std; 
 
#define n   (4000) 
#define lost <span style="white-space:pre">   </span>(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<ntotalnum; index++) 
    { 
        (plist+index)->bused = false; 
    } 
 
    /*初始化[1，n-lost]乱序数码表*/ 
    try 
    { 
        for(index=0; index<ntotalnum-nlostnum; 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<ntotalnum+nlost; index++) 
    { 
        (plist+index)->bused = false; 
    } 
 
    //扫描给出数列，在plist中标记 
    for(index=0; index<ntotalnum; index++) 
    { 
        (plist+*(pdata+index))->bused =true; 
    } 
 
    for(index=0; index<ntotalnum+nlost; 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<lost; index++) 
        cout<<*(presult+index)<<"\t"; 
 
    //检验结果 
    for(int index=0; index<n-lost; index++) 
    { 
        for(int c=0; c<lost; c++) 
        { 
            if(*(pdata+index) == *(presult+c)) 
                cout<<endl<<"结果检验错误"; 
        } 
    } 
 
    delete pdata; 
    delete presult; 
    return 1; 
} 

摘自 shyandsy的无边海洋