题目描述

小明想知道在他笔记本上写的 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 条题目来讲述如何处理众数问题。前面已经讲述了基于数组统计法和连续性分析两个方法来找到众数，现在讲解第 3 个方法：基于结构体来整理数据。其实，这个方法的名字是我自己说的，应该没有这么一种算法，归根到底，这个段代码的核心还是连续性分析，但是它的两点在于把数据整理了一遍，放入结构体，有时候，我们并不是要找众数，而是要基于这些整理出来的结构体进一步做后面的别的运算。

完成程序

#include<bits/stdc++.h>
using namespace std;
struct Num
{
	int num,cnt; //num用来存放出现过的数字，cnt用来记录这个数字出现了多少次 
}x[100001];//极端情况下，n 个数各不相同，所以就要 n 个结构体变量来存放 
int a[100001],cnt;
int main()
{
	int n,i,ans=0,MAX=0;
	scanf("%d",&n);

	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);

	sort(a+1,a+1+n);
	
	//第一个数字是 a[1]，最少有 1 个 
	x[1].num = a[1];
	x[1].cnt = 1;
	tot = 1; // tot 记录着有多少个不同的数字 

	for(i=填空(1);i<=n;i++)
	{
		if( 填空(2) ) //这是一个新的数字 
		{
			x[填空(3)].num = a[i];
			x[填空(4)].cnt = 1;
		}
		else //这是一个相同的数字 
			x[tot].cnt++;
	}
	
	//找最大值
	for(i=1;i<=tot;i++)
		if(x[i].cnt>MAX)
		{
			MAX = x[i].cnt;
			ans = 填空(5);
		}

	printf("%d",ans);

	return 0;
}

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

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

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

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

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