本文主要是介绍浙大PAT 1067题 1067. Sort with Swap(0,*)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
该题的思路很容易想到，不过若不注重技巧会超时。
若用数组v[]来容纳所有元素，该题目的目的就是通过最少的交换次数（注意只能必须是0与另一个数交换）
来使得对于所有i均有v[i]== i,既然要求得最少交换次数，那就该尽量使每一次交换都能有一个元素被换到正确位置
（且该元素不会再次被交换），下面分两种情况讨论：
1. v[0] != 0:
说明0不在正确位置上，那要通过变换使得v[0] == 0才行。此时该将0与该处在0所处的位置上的元素进行
交换，例如上面的举例{4, 0, 2, 1, 3}，此时该将0与1（0所处的位置序号为1，即这本该是1所在的位置）交换，
通过类似的多次交换直到v[0] == 0;
2. v[0] == 0:此时0已在正确位置上了，但其他元素还没有全处于正确位置。所以必须得有一次废交换了（即交换后没能使一个元素到达正确位置），怎么交换，肯定不能将0与一个已处在正确位置的元素交换吧（要不还得将这个元素交换回来），所以肯定是将0与一个处于不正确位置的元素交换。#include <stdio.h> int findNotOK(int* arr,int begin,int end){ //从begin开始往后寻找未到位的数for(int i=begin;i<end;i++){if(arr[i]!=i)return i;}return 0; }int main(){int n;scanf("%d",&n);int* arr = new int[n];int i,t;for(i=0;i<n;i++){scanf("%d",&t);arr[t]=i;}int tmp = 0;int count=0;int firstPos = 1;firstPos = findNotOK(arr,firstPos,n);while(firstPos){ //还有未到位的数字if(arr[0]==0){ //如果0到位了，则与未到位的firstPos交换 arr[0] = arr[firstPos];arr[firstPos] = 0;count++;}while(arr[0]!=0){ //如果0不到位，则循环与自己所指向的值交换tmp = arr[0];arr[0] = arr[tmp];arr[tmp] = tmp;count++;}firstPos = findNotOK(arr,firstPos,n); //此时0归位了，找到下一个未到位的数字}printf("%d\n",count);return 0; }
这篇关于浙大PAT 1067题 1067. Sort with Swap(0,*)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
