当前位置: 代码迷 >> 综合 >> HAUT OJ 1321: Choice学姐的众数问题
  详细解决方案

HAUT OJ 1321: Choice学姐的众数问题

热度:100   发布时间:2023-12-04 03:21:36.0


问题描述:

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;
}