题目描述

小明想知道在他笔记本上写的 n 个整数中出现次数最多的数是多少，如果有多个数出现次数并列最多，他想知道数最小的那个。

输入格式

第一行，一个正整数 n

第二行， n 个整数 $a_i$，表示小明的笔记本上的整数

数据范围

对于 50% 的数据， 1 ≤ n ≤ ${10}^5$ , 0 ≤ $a_i$ ≤ ${10}^6$

对于 100% 的数据， 1 ≤ n ≤ ${10}^5$ , -${10}^6$ ≤ $a_i$ ≤ ${10}^6$

输出格式

一个整数，表示答案。

样例

15
1 7 2 4 7 1 3 6 3 2 3 7 4 5 1

1

题目分析

这其实就是统计学里面的求 众数 ，所谓众数，就是在一堆数字（样本）中，出现次数最多的那个数。本来，众数是可以有多个的，所以，当有多个数字出现次数一样多的时候，题目一般会做一些变化，例如让你输出最小的那个，或者输出最大的那个，或者这几个众数都输出，这些是小变化。

我们用 4 条题目来讲述如何处理众数问题。本题讲述的是如何基于数组统计法的方法来找到众数。

我们对数组统计法其实已经很熟悉了，但是本题有一些特殊，就是数字可能是负数，所以没办法直接把数字 $a_i$ 作为数组的下标。

但是，如果我们稍加分析，也容易处理。因为 -${10}^6$ ≤ $a_i$ ≤ ${10}^6$ ,所以我们对每一个 $a_i$ 都加 -${10}^6$ ,我们假设一下这个修改过的数字叫 $b_i$ 吧，$b_i$ 的范围是 [0, 2*${10}^6$] , 我们就可以找出 $b_i$ 的众数，最后从 $b_i$ 的众数反推出 $a_i$ 的众数。

完成程序

#include<bits/stdc++.h>
using namespace std;
int x[填空(1)]; //根据 bi 的范围来定义统计数组
int main()
{
	int n,i,t,MAX=0,ans;
	scanf("%d",&n);

	for(i=1;i<=n;i++)
	{
		scanf("%d",&t);
		t += 1000000;
		填空(2) ; //数组统计
		
		if(填空(3)||(x[t]==MAX&&填空(4))) //数字出现的次数更多，或者是次数一样多，但是对应的数字是一个更小的数字
		{
			MAX = x[t]; //刷新数字最大出现次数
			ans = t; // 刷新众数
		}
	}

	printf("%d",填空(5) );

	return 0;
}

填空(1): {{ input(1) }}

填空(2): {{ input(2) }}

填空(3): {{ input(3) }}

填空(4): {{ input(4) }}

填空(5): {{ input(5) }}