思路
- 用
map
存下数字第一次出现的位置,再用结构体存下数字的值与出现次数。 - 排序,输出。
这里简单介绍一下 map
。map
本质上就像一个数组,
只不过你可以自己定义键和值 (其实就是下标与它所对应的元素) 类型。
map<string,int> mp;
这样你就有了一个可以用 string 类型映射到 int 类型的 map
数组 \(mp\) 。
mp["hello"] = 532;
这意味着在 \(mp\) 数组里,
\(\mathtt{"hello"}\) 对应着 \(\mathtt{532}\)
。
mp.count("hello");
mp.count("world");
判断该元素之前是否存在映射。
返回值分别为 \(\mathtt{1}\) 和 \(\mathtt{0}\)。
\(Code\)
#include<bits/stdc++.h>
using namespace std;
int n,m,a;
int sum; //一共出现了多少个不同的数字,同时可以辅助存储数字首次出现的位置
map<int,int> fir; //存储数字第一次出现的位置
struct num
{
int val;
int cnt; //存储数字出现的次数
} f[1005];
bool cmp(num a,num b) //排序函数
{
if(a.cnt!=b.cnt) return a.cnt>b.cnt;
else return fir[a.val]<fir[b.val];
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>a;
if(fir.count(a)) //如果此前已经出现过
{
f[fir[a]].cnt++; //次数++
}
else
{
fir[a] = ++sum; //出现的位置
f[sum] = {a,1};
}
}
sort(f+1,f+1+sum,cmp);
for(int i=1;i<=sum;i++)
{
while(f[i].cnt--) cout<<f[i].val<<" "; //重复输出相同的数字
}
cout<<endl;
return 0;
}