题目原文
问题描述（题目链接登陆账号有问题，要从这个链接登陆，然后点击“模拟考试”，进去找本题目）
| 试题编号： | 201312-1 |
| 试题名称： | 出现次数最多的数 |
| 时间限制： | 1.0s |
| 内存限制： | 256.0MB |
| 问题描述： |
问题描述
给定n个正整数，找出它们中出现次数最多的数。如果这样的数有多个，请输出其中最小的一个。
输入格式
输入的第一行只有一个正整数n(1 ≤ n ≤ 1000)，表示数字的个数。
输入的第二行有n个整数s1, s2, …, sn (1 ≤ si ≤ 10000, 1 ≤ i ≤ n)。相邻的数用空格分隔。 输出格式
输出这n个次数中出现次数最多的数。如果这样的数有多个，输出其中最小的一个。
样例输入
6
10 1 10 20 30 20 样例输出
10
|
题目大意
给你一个数n，随后给出n个正整数，让你找出众数（出现次数最多的数），如果有多个，则输出最小的
解题思路
开一个number数组，大小为数组的最大值（acm那会有一个约定俗成的说法，开数组一般比最大数值多50个空间，这里我开10050），初始值均为0，代表现在所有数字出现次数均为0（还没出现数字），遍历循环，每输入一个数字number数组对应值就自+1，比如输入5，则number[5] ++，表示出现次数加一。
接着遍历1到10000，由于是从小到大遍历，后面有资格将我替换掉的只有出现次数比我多的某个数字（相等都不行），比如3 5 5 4 4 6 9 7 7 2这组数据，从小到大遍历（1~10000），到4的时候出现2次，暂时将4记录到max变量（max代表出现次数最多），再继续到5，再继续到7，5和7都没有4出现的次数多（次数相等），所以不做交换。这种写法很好的将
如果这样的数有多个，请输出其中最小的一个
给表达出来了，如果是相等也替换则最后输出的是若干个出现次数相等的数中的最大的一个。
AC代码
1 #include<cstdio> 2 #include<cstring> 3 int number[10050]; 4 int max; 5 int main() 6 { 7 int n; 8 int x; 9 while(scanf("%d", &n) != EOF) 10 { 11 max = 0; 12 memset(number, 0, sizeof(number)); 13 for(int i = 0; i < n; i ++) 14 { 15 scanf("%d", &x); 16 number[x] ++; 17 } 18 19 for(int i = 1; i < 10050; i ++) 20 { 21 if(number[i] > number[max]){ 22 max = i; 23 } 24 } 25 printf("%d ", max); 26 } 27 }
附录
主要记录思考整个过程，从读题到有第一个思路，到逐渐调试改错，到最后想出或者看题解提示找到正确思路并且AC的完整过程
关于二维数组，先说一下，a[10][2]，和a[10][10]。
在CCF I’m stuck!中就有遇到过这个问题。
十行两列就是a[10][2]，而第二列可以为任意数字，假设为7，那我总会写成a[10][7]，这其实是一个很明显很简单的错误，但我总犯。
正常是只有两列a[n][0],a[n][1]这样。
我首先想到，用number数组记录这n个数字，用exist二维数组数组记录某数出现多少次。对于exist数组我先想到的是开exist[10050][1050]，即某个数字（第一维，最大是10000，多开一点写10050）出现（第二维最多n次，n最大1000，多开一点写1050）多少次。eg：7出现8次，则exist[7][8]。这样好像没法调这个具体数值8啊，其实exist[x][y]只是一个标号，具体要赋值给某一行某一列，给出数值，而不是把数值写到维度里面。
（错误思路）具体说一下第一次的思路吧，我开exist[10050][2]数组（这里与上面错误不同，这里不开1050而开10050是循环的时候内部就处理，比如先输入71，那么exist[71][0]赋值为71，exist[71][1]++，再输入71的话，同样执行这两条语句，比开1050遍历n往下0,1,2,3..的输入数字方便），for遍历输入，对于每一个输入我直接第一维的标号就给赋值（输入的具体数字）了，第二维作为出现次数++，然后紧接着就在循环里面判断是否 已经记录的次数比输入的数字出现次数少 并且 记录的最大数值 大于 输入的数值，是的话交换，最后整个输入结束，输出记录的出现最多的数字。
30分
1 #include<cstdio> 2 int number[1050]; 3 4 //int exist[1050][2];//二维数组挺大的学问,回忆CCF I’m stuck! 5 int exist[10050][2];//二维数组挺大的学问 http://c.biancheng.net/cpp/html/51.html 6 7 int the_number_of_occurrences;//出现的次数 8 int most_frequent_number = 10000;//出现次数最多的数字 9 int main() 10 { 11 int n; 12 scanf("%d", &n); 13 for(int i = 0; i < n; i ++) 14 { 15 scanf("%d", &number[i]); 16 exist[number[i]][0] = number[i]; 17 exist[number[i]][1] ++; 18 if(the_number_of_occurrences <= exist[number[i]][1] && most_frequent_number > exist[number[i]][0]) 19 { 20 the_number_of_occurrences = exist[number[i]][1]; 21 most_frequent_number = exist[number[i]][0]; 22 } 23 } 24 printf("%d ", most_frequent_number); 25 }
问题很多很多，思路有严重问题，随便举一个反例7 7 5 5 1 7最后实际输出5
主要问题有两点就是
1.if那个并“&&”思维错误，不能这么判断。
2.要累计完再判断，不能边输入边判断。
加了个等号40分了？？？？不对 啊
1 #include<cstdio> 2 int number[1050]; 3 4 //int exist[1050][2];//二维数组挺大的学问,回忆CCF I’m stuck! 5 int exist[10050][2];//二维数组挺大的学问 http://c.biancheng.net/cpp/html/51.html 6 7 int the_number_of_occurrences;//出现的次数 8 int most_frequent_number = 10050;//出现次数最多的数字 9 int main() 10 { 11 int n; 12 scanf("%d", &n); 13 for(int i = 0; i < n; i ++){ 14 scanf("%d", &number[i]); 15 exist[number[i]][0] = number[i]; 16 exist[number[i]][1] ++; 17 if(the_number_of_occurrences <= exist[number[i]][1] && most_frequent_number >= exist[number[i]][0]){ 18 the_number_of_occurrences = exist[number[i]][1]; 19 most_frequent_number = exist[number[i]][0]; 20 } 21 } 22 printf("%d ", most_frequent_number); 23 }
问题所在同上，一个错误思路，至于多了10分，不想了，某些特殊数据导致一些离奇的结果。
修改之后60分
1 #include<cstdio> 2 #include<cstring> 3 int number[1050]; 4 5 //int exist[1050][2];//二维数组挺大的学问,回忆CCF I’m stuck! 6 int exist[10050][2];//二维数组挺大的学问 http://c.biancheng.net/cpp/html/51.html 7 8 int the_number_of_occurrences = -1;//出现的次数 9 int most_frequent_number = 10050;//出现次数最多的数字 10 int main() 11 { 12 int n; 13 scanf("%d", &n); 14 memset(number, 0, sizeof(number)); 15 for(int i = 0; i < n; i ++){ 16 scanf("%d", &number[i]); 17 exist[number[i]][0] = number[i]; 18 exist[number[i]][1] ++; 19 } 20 for(int i = 0; i < 10001; i ++){ 21 if(the_number_of_occurrences <= exist[number[i]][1] && most_frequent_number > exist[number[i]][0]){ 22 the_number_of_occurrences = exist[number[i]][1]; 23 most_frequent_number = exist[number[i]][0]; 24 } 25 } 26 printf("%d ", most_frequent_number); 27 }
反例
问题同样在于if的判断，“&&”那里。
继续思考，那我就把if判断拆开。
将最大的出现次数单独记录出来，接着再循环，将所有同样出现次数的数字比较大小，输出最小值。
AC代码
1 #include<cstdio> 2 #include<cstring> 3 int number[1050]; 4 //int exist[1050][2];//二维数组挺大的学问,回忆CCF I’m stuck! 5 int exist[10050][2];//二维数组挺大的学问 http://c.biancheng.net/cpp/html/51.html 6 7 int maximum_number_of_occurrences = -1;//出现的最多次数 8 int most_frequent_number = 10050;//出现次数最多的数字 9 int main() 10 { 11 int n; 12 scanf("%d", &n); 13 memset(number, 0, sizeof(number)); 14 for(int i = 0; i < n; i ++){ 15 scanf("%d", &number[i]); 16 exist[number[i]][0] = number[i]; 17 exist[number[i]][1] ++; 18 } 19 // for(int i = 0; i < 10001; i ++){ 20 // if((maximum_number_of_occurrences <= exist[number[i]][1]) && (most_frequent_number > exist[number[i]][0])){ 21 // maximum_number_of_occurrences = exist[number[i]][1]; 22 // most_frequent_number = exist[number[i]][0]; 23 // } 24 // } 25 for(int i = 0; i < 10001; i ++){ 26 if((maximum_number_of_occurrences <= exist[number[i]][1])){ 27 maximum_number_of_occurrences = exist[number[i]][1]; 28 } 29 } 30 // printf("%d ", maximum_number_of_occurrences); 31 for(int i = 0; i < 10001; i ++){ 32 if(exist[i][1] == maximum_number_of_occurrences) 33 if(exist[i][0] < most_frequent_number) 34 most_frequent_number = exist[i][0]; 35 } 36 printf("%d ", most_frequent_number); 37 }
到这里已经基本结束了，但感觉思路太挫了，写的很复杂
看了一下别人的题解，学了一些新思路，清新透彻。
就是这个 博客参考
但是写的时候
学习新方法后第一次写70
1 #include<cstdio> 2 #include<cstring> 3 int number[10050]; 4 int max = 0; 5 int main() 6 { 7 int n; 8 int x; 9 scanf("%d", &n); 10 memset(number, 0, sizeof(number)); 11 for(int i = 0; i < n; i ++){ 12 scanf("%d", &x); 13 number[x] ++; 14 } 15 for(int i = 0; i < 10001; i ++){ 16 if(number[i] > max) 17 max = i; 18 } 19 printf("%d ", max); 20 }
问题在于，16，17行出现错误。其实明显错误，随便一个反例（1 4 4 2 1 1）就可以看出来。输出4，其实应该是1的。
max不要设置成-1，比较交换是真正有意义真正存在的数字，而如果max设置为-1，第一次比较就会交换吗，哪怕没有数字，比如输入4 7 2 7，这里没有1，number[1]是0，而-1<0必然交换，这其实是一个伪交换，不知道会引发什么错误。
第一次AC代码（拿编译器当草纸），简单优化一下就是上面的AC代码了
1 #include<cstdio> 2 #include<cstring> 3 int number[10050]; 4 int max = 0; 5 int main() 6 { 7 int n; 8 int x; 9 int answer; 10 while(scanf("%d", &n) != EOF) 11 { 12 13 memset(number, 0, sizeof(number)); 14 for(int i = 0; i < n; i ++) 15 { 16 scanf("%d", &x); 17 if(i == 0) 18 answer = x; 19 number[x] ++; 20 } 21 22 // for(int i = 1; i < 7; i ++){ 23 // printf("%d ", number[i]); 24 // } 25 //printf(" "); 26 for(int i = 1; i < 10050; i ++) 27 { 28 if(number[i] > max){ 29 max = number[i]; 30 answer = i; 31 // printf("%d %d ", i ,max); 32 } 33 } 34 //printf(" "); 35 printf("%d ", answer); 36 } 37 }