A22563. 简单排序题（easy）
填空题
较难
知识点
题目描述
简单排序题（easy）
题目描述
给定n(1 ≤n≤5×10^5) 个正整数，第 i 个数字为ai(1≤ai ≤10^9)。请对他们进行排序。其中排序ai和aj（i<j) 的规则为：如果ai这个数字出现次数和aj的出现次数相同，则ai排在前面。否则把出现次数多的排在前面。
输入格式
第一行一个正整数n表示要排序的数字数量。
接下来一行n个正整数表示要排序的数字ai。
输出格式
输出一行n个正整数表示排序后的数字。
样例输入1
6
1 2 1 2 2 1样例输出1
1 2 1 2 2 1样例输入2
7
2 3 1 1 3 2 1样例输出2
1 1 1 2 3 3 2说明/提示
【样例1解释】由于1和2的出现次数相同，因此相对顺序不变。
【样例2解释】由于1的出现次数比2和3多，因此1会被排在2和3前面。23由于出现次数相同，因此相对位置不变。
参考答案
#include<bits/stdc++.h>
using namespace std;
struct num{
int cnt;//出现次数
int n;//这个数字本身
int id;//编号
}a[500005];
map<int,int>mp;//数与次数的关系
bool cmp(num x,num y){
if(x.cnt!=y.cnt){
return x.cnt>y.cnt;//按出现次数降序
}else{
return x.id<y.id;//按照编号升序
}
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i].n);
mp[a[i].n]++;//利用map记录次数
a[i].id=i;//记录输入顺序
}
for(int i=1;i<=n;i++){//更新结构体中的cnt信息
a[i].cnt=mp[a[i].n];
}
sort(a+1,a+1+n,cmp);//结构体排序
for(int i=1;i<=n;i++){
cout<<a[i].n<<" ";
}
return 0;
}
上一题
下一题