题解_计数排序

观察题目不难发现两个关键词：“去重”&“排序”；把这两个关键词结合一下不难联想到桶排序、计数排序&基数排序。下面是一种计数排序的写法：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+100;
int n;
int ans;//统计不同随机数的个数 
bool Counting[N];//去重+计数排序
int maxn = -1;//记录输入随机数的最大值，剪枝计数排序 
void Counting_Sort()
{
	for(int i = 1;i <= maxn;i++)
	{
		if(Counting[i])
			cout << i << ' ';
	}
}
int main()
{
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		int a;
		cin >> a;
		if(!Counting[a])
		{
			ans++;
			Counting[a] = 1; 
		}
		maxn = max(maxn,a);
	}
    cout << ans << endl;
	Counting_Sort();
	return 0;
}