CCF CSP 201503-2.数字排序

问题描述

　　给定n个整数，请统计出每个整数出现的次数，按出现次数从多到少的顺序输出。

输入格式

　　输入的第一行包含一个整数n，表示给定数字的个数。
　　第二行包含n个整数，相邻的整数之间用一个空格分隔，表示所给定的整数。

输出格式

　　输出多行，每行包含两个整数，分别表示一个给定的整数和它出现的次数。按出现次数递减的顺序输出。如果两个整数出现的次数一样多，则先输出值较小的，然后输出值较大的。

样例输入

12
5 2 3 3 1 3 4 2 5 2 3 5

样例输出

3 4
2 3
5 3
1 1
4 1

评测用例规模与约定

　　1 ≤ n ≤ 1000，给出的数都是不超过1000的非负整数。

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

typedef struct Node {
	int num;
	int count;
	Node(int _num, int _count) {
		num = _num;
		count = _count;
	}
} Pair;
// 按照出现次数从大到小排序，若次数相同，则按照值从小到大的顺序排列
bool cmp(Pair a, Pair b) {
	if (a.count != b.count) {
		return a.count > b.count;
	}
	return a.num < b.num;
}

int main() {
	int n, data;
	scanf("%d", &n);
	vector<Pair> arr;
	while (n--) {
		scanf("%d", &data);
		// 判断data是否已经存在
		bool flag = false;
		for (int i = 0; i < arr.size(); i++) {
			// 若data已经在arr中，则增加出现次数
			if (arr[i].num == data) {
				arr[i].count++;
				flag = true;
				break;
			}
		}
		// 若data不在arr中
		if (!flag) {
			arr.push_back(Pair(data, 1));
		}
	}
	// 排序
	sort(arr.begin(), arr.end(), cmp);

	for (int i = 0; i < arr.size(); i++) {
		printf("%d %d\n", arr[i].num, arr[i].count);
	}
	return 0;
}