黑马程序员技术交流社区

标题: 有1000000个数,每个数的取值范围都是0~999999,找出其中重复的数 [打印本页]

---

作者: 余丽丽    时间: 2015-8-9 09:33
标题: 有1000000个数,每个数的取值范围都是0~999999,找出其中重复的数
#define COUNT 1000000

int main(void)
{
            inta[COUNT] = {0};
   for (int i = 0; i < COUNT; i++) {
       int number = arc4random()%COUNT;//把随机数作为下标，值作为出现次数
       a[number - 1] ++;
    }
   //输出重复的数字以及重复次数
   for(int i = 0 ;i < COUNT;i++){
       if (a[i] > 1) {
           printf("%d repeats %d times\n",i+1,a[i]);
       }
    }
            return0;
}


这种效率比较高，有的人用类似冒泡排序的方法，理论上可以实现，但是CPU的运算速度达不到，程序会一直卡在那里

---

作者: wowthe1st    时间: 2015-8-9 11:46
这样解决的问题不一样啊，排序解决的是已知的1M个数里面重复的，
你这个解决的是，1M个随机数里面重复的，每次结果都不一样

---

作者: wowthe1st    时间: 2015-8-9 11:52
当然用冒泡或插入排1M个数基本都不现实，排个几千上W个就卡了；
基本会用其他算法排序，IOS中还不知道怎么弄，java中有自己的很快的排序方式

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2