/******************************************************************************* 文 件 名 : test100.cpp 實(shí)現(xiàn)功能 : 微軟面試題：有100萬(wàn)個(gè)數(shù)字（1到9），其中只有1個(gè)數(shù)字重復(fù)2次，如何快速找出該數(shù)字補(bǔ)充下題目 意思：我這里每個(gè)數(shù)字 都是個(gè)阿拉伯?dāng)?shù)字,是1位的,是1到9之間的但是有1百萬(wàn)個(gè)這樣的數(shù)字 比如 12345678912 是11個(gè)這樣的數(shù)字 實(shí)現(xiàn)思路 : 定義9個(gè)數(shù)組，記錄1-9的出現(xiàn)的數(shù)字做標(biāo)記，出現(xiàn)一次則，對(duì)應(yīng)數(shù)組加1，超過(guò)2次，在下次循環(huán)直接結(jié)束，這樣一共直到記錄8個(gè)數(shù)字后，直接打印第9個(gè)數(shù)字，就是一共只會(huì)出現(xiàn)2次的數(shù)字了 作 者 : jernymy 版 權(quán) : <Copyright(C) ... jernymy.> 日 期 : 2011-07-28 版 本 : V1.0 *******************************************************************************/#include "stdio.h" #include "stdlib.h" // srand #include "time.h" // time #include "string.h" // memset// 最大的數(shù)據(jù)是100萬(wàn)， 1000000 #define MAX_NUM 1000*1000// 出現(xiàn)頻率的個(gè)數(shù) #define OVER_VAR 2// 記錄1-9這幾個(gè)數(shù)字出現(xiàn)的次數(shù)，是否出現(xiàn)超過(guò)2次， // 如果超過(guò)2次可以不用判斷，初始化為0 unsigned char g_abyNumAry[10];// 記錄總共出現(xiàn)超過(guò)3次的數(shù)字的個(gè)數(shù)，當(dāng)超過(guò)7個(gè)時(shí)，即為8時(shí)。 // 則可以直接打印出沒(méi)有出現(xiàn)超過(guò)2次的那個(gè)數(shù)字，就一定是公出現(xiàn)2次的數(shù)字了。 unsigned char g_nCount = 0;int main(void) {int nIdx;int nData;time_t nCurTime; srand(time(&nCurTime));memset(g_abyNumAry, 0, sizeof(g_abyNumAry));for (nIdx = 0; nIdx < MAX_NUM; nIdx++){nData = rand()%9 + 1; // 隨機(jī)數(shù)從1到9，測(cè)試專用，jernymy from 1-9printf("%d ", nData); // 打印該隨機(jī)數(shù)字// 此數(shù)字出現(xiàn)次數(shù)大于2次，則退出次循環(huán)if (g_abyNumAry[nData] > OVER_VAR){continue;}// 此數(shù)字出現(xiàn)1次，在大于2次時(shí)，就對(duì)總個(gè)數(shù)加1if (++g_abyNumAry[nData] > OVER_VAR){g_nCount++;}// 當(dāng)有8個(gè)數(shù)字出現(xiàn)的個(gè)數(shù)均超過(guò)2次，// 那么剩下的那個(gè)數(shù)字一定就是要求的了if (g_nCount == 8){printf("\nfound only 2 num: ");for (nIdx = 1; nIdx < 10; nIdx++){if (g_abyNumAry[nIdx] < (OVER_VAR+1)){// jernymy 此數(shù)就是我們要找的那個(gè)了printf("%d\n", nIdx);}}break;} }return 0; }

總結(jié)

以上是生活随笔為你收集整理的微软面试题：有100万个数字（1到9），其中只有1个数字重复2次，如何快速找出该数字的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。