求解一个序列中出现次数最多的元素问题（空间换时间）

再水一波实验。。。

一、 实验目的

1. 加深对求解一个序列中出现次数最多元素算法的理解;
2. 通过本次试验掌握将算法转换为上机操作;
3. 加深对以空间换时间思想的理解，并利用其解决生活中的问题。

二、实验内容

任务：求解一个序列中出现次数最多的元素问题

给定N个正整数，编写一个程序找出序列中出现次数最多的整数。如果这样的
数有多个，请输出其中最小的一个。

输入样例: 6 (输入整数的个数)
10 1 10 20 30 20 (输入的n个整数)

样例输出: 10

三、实验原理

首先本题就是求一个序列中出现次数最多的元素的问题，可以使用效率较高的以空间换时间的算法：

1. 在输入的同时，就进行统计每个元素出现的次数
2. 更新出现的最小值及最小次数
   a) 当前值出现的次数大于之前出现最多次数最小值的次数时，则更新
   b) 当前值出现的次数和之前出现次数最多最小值的次数相等时，则更新为较小值。

四、程序代码

说明： 以空间换时间，此程序最大输入应该在int类型数组最大允许范围内。
时间复杂度：O(N)
代码如下：

#include <iostream>
using namespace std;

const int N = 1e6;
int a[N], n, minValue, count, x; 

int main()
{
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> x; a[x]++;
		if(a[x] > count || a[x] == count && x < minValue ){
			minValue = x;
			count = a[x];
		}
	}
	cout << minValue << endl;
	return 0;
}

五、实验结果

测试一：

测试二：

六、分析总结

1. 通过本次实验掌握了求解一个序列元素出现最多次数的问题，了解了一些相关算法的实现及求解原理。
2. 最终发现以空间换时间的算法是有不足的，即输入数据太大会超出数组下标范围，发生溢出，出现不可估计的错误。所以也可以使用其他方法，在数据较大，时间要求低一点情况下，可以直接使用排序求解！