问题描述:
Choice学姐回到家里,把n种糖果分别放到箱子里,第i种糖果有mi个,她想知道mi中出现最多的那个是数是什么,你能告诉她吗?保证出现最多的那个数的出现次数大于n/2。
输入:
第一行输入一个整数n(1 <= n <= 1e6)。
接下来一行n个整数mi(1<= mi <= 1e9),表示第i种糖果的个数,整数之间用空格隔开。
(注意内存限制,众数出现的次数大于n/2)
输出:
输出mi中出现最多的那个数,占一行。
样例输入:
5 10 10 10 20 30
样例输出:
10
原因分析:
数据 n 过大,数组存下每个出现的次数,再重新循环找最大值,时间肯定超时.
所以可以 一个一个判断,拿一个变量存次数,如果相等则次数++,否则次数--,如果减为0说明该数不是众数,当然让次数--的数肯定也不是众数,举个例子: 3 3 3 2 2 1 最后次数减为0, 3 2 1 肯定也不是众数
解决方案:
#include <stdio.h>int main()
{int n, t, x, top;scanf("%d", &n);top = t = 0;for(int i = 1;i <= n; i++){scanf("%d",&x);if(x == t)top++;else if(top == 0) {t=x;top=1;}elsetop--;}printf("%d\n", t);return 0;
}