求微软面试题：有100万个数字（1到9），其中只有1个数字重复2次，怎么快速找出该数字

求微软面试题：有100万个数字（1到9），其中只有1个数字重复2次，如何快速找出该数字
数字是1到9中间的
[解决办法]
o(n)全部存好.
o(n) 找出2
[解决办法]
帮顶了
[解决办法]
抽屉原理有用么？
[解决办法]
帮顶了
[解决办法]
遍历吧。

#include&lt;stdio.h&gt;
int buf[256];
int main(int argc, char* argv[]){
int i;

while((i=getchar()) != EOF){
buf[i]++;
}

for(i='1';i&lt;'9';i++) if(buf[i]==2) printf("i==%c", i);

}

[解决办法]
楼上木有考虑等于9啊
[解决办法]
补充下题目意思：我这里每个数字都是个阿拉伯数字是1位的是 1到9之间的

但是有1百万个这样的数字比如 12345678912 是11个这样的数字
[解决办法]
搞不懂,个人觉得,对于一串无序的数,想求这玩意,必须至少遍历一遍所有的数,只不过,它给出了条件,有且只有一个数字是出现两次的,这样,我们只要找出八个重复超过三次的就行了,或者如果有数字只出现一次,个人觉得,除了慢慢遍历,没什么好方法了吧
[解决办法]
比如有
1，3，1，5，3，9，3，5，6，4，7，5，1，2，
等这样数字公100万个



/*******************************************************************************
文 件 名 : test100.cpp
实现功能 : 微软面试题：
           有100万个数字（1到9），其中只有1个数字重复2次，如何快速找出该数字
           补充下题目 意思：我这里每个数字 都是个阿拉伯数字,是1位的,是1到9之间的
           但是有1百万个这样的数字 比如 12345678912 是11个这样的数字
实现思路 : 定义9个数组，记录1-9的出现的数字做标记，出现一次则，对应数组加1，
           超过2次，在下次循环直接结束，这样一共直到记录8个数字后，
           直接打印第9个数字，就是一共只会出现2次的数字了
作    者 : jernymy
版    权 : &lt;Copyright(C) ... jernymy.&gt;
日    期 : 2011-07-28 
 
版    本 : V1.0
*******************************************************************************/

#include "stdio.h"
#include "stdlib.h"  // srand
#include "time.h"    // time
#include "string.h"  // memset

// 最大的数据是100万， 1000000
#define MAX_NUM  1000*1000

// 出现频率的个数
#define OVER_VAR  2

// 记录1-9这几个数字出现的次数，是否出现超过2次，
// 如果超过2次可以不用判断，初始化为0
unsigned char g_abyNumAry[10];

// 记录总共出现超过3次的数字的个数，当超过7个时，即为8时。
// 则可以直接打印出没有出现超过2次的那个数字，就一定是公出现2次的数字了。
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 &lt; MAX_NUM; nIdx++)
    {
        nData = rand()%9 + 1; // 随机数从1到9，测试专用，jernymy from 1-9

        printf("%d ", nData); // 打印该随机数字
        
         // 此数字出现次数大于2次，则退出次循环
         if (g_abyNumAry[nData] &gt; OVER_VAR)
        {
            continue;
        }

        // 此数字出现1次，在大于2次时，就对总个数加1
        if (++g_abyNumAry[nData] &gt; OVER_VAR)
        {
            g_nCount++;
        }
    
        // 当有8个数字出现的个数均超过2次，
         // 那么剩下的那个数字一定就是要求的了
         if (g_nCount == 8)
        {
            printf("\nfound only 2 num: ");
            for (nIdx = 1; nIdx &lt; 10; nIdx++)
            { 
 
                if (g_abyNumAry[nIdx] &lt; (OVER_VAR+1))
                {
                    // jernymy 此数就是我们要找的那个了
                    printf("%d\n", nIdx);
                }
            }
            break;
        }    
    }

    return 0;
}

http://blog.csdn.net/jernymy/article/details/5612214#
[解决办法]
写到博客上了，仅供参考
http://blog.csdn.net/jernymy/article/details/6639534

求微软面试题：有100万个数字（1到9）

热点推荐