该题的思路很容易想到,不过若不注重技巧会超时。
若用数组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;
}