题目描述

小明想知道在他笔记本上写的 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 条题目来讲述如何处理众数问题。本题讲述的是如何基于连续性分析的方法来找到众数。

我们先对数字排序，排序前，数字为：

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

排序后，就会变成

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

我们看这串数字是不是比较有有感觉，我们发现数字好像是由若干段组成，每一段是相同的一段数字。一段数字，一个数字连续出现了 3 次，我们就说这一段长度为 3 。最后，我们就是找长度最长的那一段。既然这样，就可以套用我们以前学过的连续性分析的算法了。

完成程序

#include<bits/stdc++.h>
using namespace std;
int x[100002]; //这里我故意把数组定义大了一丢丢
int main()
{
	int n,i,ans=0,p;
	scanf("%d",&n);

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

	sort(x+1,x+1+n);
	
	x[++n] = 100000000; //这个数字比题目中的最大 ai 还要大，这里把 n 增加了1，为了方便计算最后一段 
	p=1; // p 记录着一段相同的数字是从什么地方开始的
    int MAX=0; // MAX 是记录着最大长度的
	for(i=2;i<=n;i++)
	{
		if( 填空(1)) // 后项不等于前项，说明出现了一个新的数字
		{
			if(MAX< 填空(2) ) //从p开始，到i-1 是连续相同的数字 x[p] ,它的长度比 MAX 更长 
			{
				ans = x[p]; //刷新众数
				填空(3) ;  // 刷新最大长度 
			}
			p = 填空(4) ;  // 从 i 开始是新的一段连续数字
		}
	}

	printf("%d",ans);

	return 0;
}

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

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

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

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