众数问题 oj17

众数问题

发布时间: 2017年5月25日 19:57   最后更新: 2017年5月26日 00:08   时间限制: 1000ms   内存限制: 128M

描述

问题描述： 
给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。 
例如，S={1，2，2，2，3，5}。多重集S的众数是2，其重数为3。 
编程任务： 
对于给定的由n 个自然数组成的多重集S，编程计算S 的众数及其重数。

输入

第1行多重集S中元素个数n(n<=50000)；接下来的n 行中，每行有一个自然数。

输出

输出文件有2 行，第1 行给出众数，第2 行是重数。(如果有多个众数，只输出最小的)

样例输入1 复制

6
1
2
2
2
3
5

样例输出1

2
3

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int cmp(int a, int b)
{
	return a < b;
}
int main()
{
	int n;
	cin >> n;
	vector<int> iter;
	vector<int>::iterator pIter;
	int *f = new int[n];
	int num;
	for (int i = 0; i < n; i++)
	{
		f[i] = 1;
		scanf("%d", &num);
		iter.push_back(num);
	}
	sort(iter.begin(), iter.end(), cmp);
	for (int i = 0; i < n - 1; i++)
	{
		pIter = iter.begin();
		for (int j = i + 1; j < n; j++)
		{
			if (pIter[i] == pIter[j])
			{
				f[i]++;
				iter.erase(pIter + 1);
				j--;
				n = n - f[i] + 1;
			}
		}

	}
	pIter = iter.begin();
	int  index,flag=0;
	for (int i = 0; i<iter.size(); i++)
	{
		if (f[i] != 1)
		{
			index = i;
			flag = 1;
			break;
		}
	}
	pIter = iter.begin();
	if (!flag)
	{
		vector<int>::iterator smallest = min_element(iter.begin(), iter.end());
		index = distance(iter.begin(), smallest);
	}
	pIter = iter.begin();
	cout << pIter[index] << endl << f[index];
	return 0;
}