三值排序
发布日期:2022-02-25 01:17:45 浏览次数:23 分类:技术文章

本文共 983 字,大约阅读时间需要 3 分钟。

排序是一种很频繁的计算任务。一个实际的例子是,当我们给某项竞赛的优胜者按金银铜牌排序的时候。在这个任务中可能的值只有三种1,2和3。我们用交换的方法把他排成升序的。

写一个程序计算出,计算出的一个包括1、2、3三种值的数字序列,排成升序所需的最少交换次数。

输入第1行为类别的数量N(1≤N≤1000)

输入第2行到第N+1行,每行包括一个数字(1或2或3)。

输出包含一行,为排成升序所需的最少交换次数。

样例输入

9221333231

样例输出

4

解题思路

又是一道入门的贪心题,不过本弱鸡却一直没有思路很久才做了出来,在参考了大佬的思路后才做了出来。大佬的思路是开一个数组里的数字排好序,然后跟原数组进行位置比较,如果不对就将原数组里的数字换过去。

#include
   
    using namespace std;int main(){
    
int n;
int a[1005],b[1005];
int cnt,index; 
cin>>n;
for(int i = 1;i <= n;i++){
cin>>a[i];
}
memcpy(b,a,sizeof(b));
sort(b + 1,b + 1 + n);//确定该数组里的数字本该存在的位置 
cnt = 0;
for(int i = 1;i <= n;i++){
if(a[i] != b[i]){
index = 0;
for(int j = n;j >= i + 1;j--){
if(a[j] == b[i] && b[i] != b[j]){
//printf("a[%d] = %d b[%d] = %d\n",j,a[j],j,b[i]); 
index = j;
if(a[i] == b[j]){
break;
}
}
}
swap(a[i],a[index]);
cnt++;
}
}
cout< <
return 0;} //9 2 2 1 3 3 3 2 3 1 //  1 1 2 2 2 3 3 3 3

转载地址:https://blog.csdn.net/qq_37755550/article/details/80207519 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:最大子阵列
下一篇:法师康的工人

发表评论

最新留言

很好
[***.229.124.182]2023年01月25日 02时18分01秒