题目描述

小明想知道在他笔记本上写的 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

3

题目分析

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

我们用 4 条题目来讲述如何处理众数问题。第三种方法是基于结构体的来做数据整理，结构体里面包含了 2 个成员变量，一个是 num ，代表的是出现过什么数字，第二个是 cnt ，代表这个数字出现过多少次。从整理的结果来看，这个结构体数组就很像是数组统计的结果（从整理的过程来看，是基于连续性分析的算法）。对于学过映射（ STL MAP ）的同学来看，这个整理的过程可以交给 STL MAP 模板去做，节省一些代码。

map 是从一个数据到另外一个数据的映射。其实，我们的数组就很想是一个映射，例如 int a[10]; a[2] = 5 ; 这里实际上我们是把 2 映射到了 5。另外一个例子 string a[100];a[11]="li si";a[12]="zhang san"; 我们可以理解为用 11 映射到了 "li si", 用 12 映射到了 "zhang san"。中括号里面的内容我们称为 key ， 映射的结果我们称为 value 。数组，就是一系列的 key:value 对，只不过，key 是连续的整数。例如，你定义数组 int a[100]; 那么 key 只能是 0 到 99 ，超出这个范围就是错的。另外，数组的 key (下标一定是正整数，不能是别的数据类型）。 STL 的 map 模板正式解决这些问题的。

本题的数据有负数，所以，用 map 刚好能解决。

完成程序

#include<bits/stdc++.h>
using namespace std;
map <int,int> m;
int n; 
int main()
{
	scanf("%d",&n);
	int i,t,ans;
	for(i=0;i<n;i++)
	{
		scanf("%d",&t);
		填空(1) ; //类似数组统计 
	}
	
	map <int,int> ::iterator it ; //定义迭代器，用于访问 STL 对象	
	
	int MAX=0;
	for(it=填空(2) ;it!=填空(3) ;it++)
	{
		if( 填空(4)) //刷最大值
		{
			MAX = 填空(5) ;
			ans = 填空(6) ;
		}
	}

	cout<<ans;
	return 0;
}

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

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

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

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

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

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