問題描述:有一組數字,從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;
}