数组排序 --- 庞果

桃扇骨 2022-03-29 06:27 186阅读 0赞

### 题目说明 ###

--------------------

本题来自caopengcs，只要你有兴趣，每个人都可以出题（出题入口在主页右侧边栏“贡献题目”内），以下是题目详情：

给定一个包含1-n的数列，我们通过交换任意两个元素给数列重新排序。

求最少需要多少次交换，能把数组排成按1-n递增的顺序，其中，数组长度不超过100。

例如：

*  原数组是3,2,1， 我们只需要交换1和3就行了，交换次数为1，所以输出1。
 *  原数组是2,3,1，我们需要交换2和1，变成1,3,2，再交换3和2，变为1，2，3，总共需要的交换次数为2，所以输出2。

函数头部： C/C++ int run(const int \*a,int n);

### 算法描述 ###

--------------------

实际上，这个题目是一个N个连续数的排序，题目中有个条件需要注意一下，比如四个数，肯定是1，2，3，4这四个，不会是1,3,4,5，所以是连续数的排序，要做到交换次数最少，需要做到的只有一点： **每次交换后，交换的数中至少有一个数不需要在动了，也就是每次交换都要有直接的效果**， 为了满足这个条件，我们可以这么来交换：

*  先把“1”交换到位置“1”上
 *  然后依次把各个数交换到他们自己的位置上
 *  位置上正好是这个数的不需要交换

满足上面三点要求并进行交换就行了。

代码很简单，也没做什么优化，都传到github上了。

int run(const int *a,int n)
    {
    	int *b=(int *)malloc(sizeof(int)*n);
    	int count=0;
    	int temp;
    	for(int i=0;i<n;i++)
    		b[i]=a[i];
    	
    	
    	for(int i=0;i<n;i++)
    	{
    		for(int k=i;k<n;k++)
    		{
    			if(b[k]==i+1 && k!=i)
    			{
    				count++;
    				temp=b[k];
    				b[k]=b[i];
    				b[i]=temp;
    			}
    		}
    	}
    	
    	return count;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，186人围观）

还没有评论，来说两句吧...

相关阅读

相关数组排序

<script> export default { data() { return { pxarr: [1, 4, -8,

谁借莪１个温暖的怀抱￠/ 2023年02月22日 12:14/ 0 赞/ 157 阅读

相关【三国演义】——周瑜、庞统

周瑜，子公瑾，吴国大都督，夫人小乔，自幼与孙策玩耍，后跟随孙策，与其称兄道弟，一起南征北战，共创东吴大好河山，孙策死后，全力辅佐孙权，擅长水战，在东吴人气颇高。相关章节：赤

绝地灬酷狼/ 2022年11月16日 15:20/ 0 赞/ 51 阅读

相关数组排序

var arr = [ {a:'xx',b:10}, {a:'dd',b:28}, {a:'cc',b:38}

矫情吗；*/ 2022年06月03日 09:21/ 0 赞/ 184 阅读

相关数组排序

冒泡排序 for(int i = 0; i < a.length - 1; i++) { for(int j = 0; j < a.length

朱雀/ 2022年05月16日 01:06/ 0 赞/ 206 阅读

相关庞果网之建立信号基站

题目详情要建立一个信号基站服务n个村庄，这n个村庄用平面上的n个点表示。假设基站建立的位置在(X,Y)，则它对某个村庄(x,y)的距离为max\{|X – x|, |Y –

曾经终败给现在/ 2022年05月13日 00:04/ 0 赞/ 153 阅读

相关庞果网之数组排序

题目详情本题来自caopengcs，只要你有兴趣，每个人都可以出题（出题入口在主页右侧边栏“贡献题目”->“我要发布”内），以下是题目详情：给定一个包含1-n的数列，我

我不是女神ヾ/ 2022年05月13日 00:00/ 0 赞/ 151 阅读

相关庞果网之字符串消除

题目详情给定一个字符串，仅由a,b,c 3种小写字母组成。当出现连续两个不同的字母时，你可以用另外一个字母替换它，如 1. 有ab或ba连续出现，你把它们替换

灰太狼/ 2022年05月13日 00:00/ 0 赞/ 136 阅读

相关庞果网之字符串的完美度

题目详情我们要给每个字母配一个1-26之间的整数，具体怎么分配由你决定，但不同字母的完美度不同，而一个字符串的完美度等于它里面所有字母的完美度之和，且不在乎字母大小写，

灰太狼/ 2022年05月13日 00:00/ 0 赞/ 147 阅读

相关数组排序 --- 庞果

题目说明 -------------------- 本题来自caopengcs，只要你有兴趣，每个人都可以出题（出题入口在主页右侧边栏“贡献题目”内），以下是题目详情：

桃扇骨/ 2022年03月29日 06:27/ 0 赞/ 187 阅读

相关数组排序

package cn.com.collections.sort; import java.util.Arrays; public c

淩亂°似流年/ 2022年02月05日 13:41/ 0 赞/ 231 阅读