程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 解一道面試題

解一道面試題

編輯:關於C語言

問題描述:有一組數字,從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的無邊海洋

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved