贪心的作用:保证每一次置换有至少一个点的值变为正确的即可
for(int i = 1; i <= n; i++){
if(a[i] != i){
// 交换i位置和a[i]对应值的位置
int t = a[a[i]];
a[a[i]] = a[i];
a[i] = t;
res++;
i--;
}
}
即如果 a[1]
的值为9,设定原本应该为1,那么直接把9换到 a[9]
的下面,这样就确保了每次置换至少确定了一个点的位置,这个时候置换次数 + 1,即 res++
。
但是由于无法确定 a[9]
的值一定是1,所以需要 i--
再次确定a[1]的值
~其实就是表面上由前往后遍历,实际上位置的确定是随机的~
完整代码如下
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main{
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
static final int N = 10010;
static int n;
static int[] a = new int[N];
public static int Int(String s){return Integer.parseInt(s);}
public static void main(String[] args) throws IOException{
n = Int(in.readLine());
String[] s = in.readLine().split(" ");
for(int i = 1; i <= n; i++) a[i] = Int(s[i - 1]);
int res = 0;
// j作为新数组的已排序的标志位
for(int i = 1; i <= n; i++){
if(a[i] != i){
// 交换i位置和a[i]对应值的位置
int t = a[a[i]];
a[a[i]] = a[i];
a[i] = t;
res++;
i--;
}
}
out.write(res + "\n");
out.flush();
}
}