OJ练习(2)————最小交换次数

OJ练习(2)————最小交换次数

描述

给定一个由N个不同的elements组成的数组，找到对数组进行排序所需的最小交换次数。您需要完成该函数，该函数返回一个表示对数组进行排序所需的最小交换次数的整数。

思路

首先对队列进行排序，排完序之后，与原序列比较。从左向右将不在自己位置上的数字交换到自己位置上即可。
如 5 1 3 2 4 排序后为 1 2 3 4 5
先将第一位归为 即把1 5互换，为 1 5 3 2 4
再看第二位 把 2 5 互换， 为 1 2 3 5 4
再看第三位 正确就不管
第四位 把 5 4互换，整个序列变为 1 2 3 4 5，与有序序列相同。交换停止

Solution

public void Solution(int [] a){int num = a.length;int [] order = new int[num];for (int i = 0; i < num; i++) {order[i] = a[i];}Arrays.sort(order);int count = 0;for (int j = 0; j < num; j++) {if (order[j]!=a[j]) {for (int k = j; k < num; k++) {if (a[k]==order[j]) {int temp = a[k];a[k] = a[j];a[j] = temp;count++;}}}}System.out.println(count);
}

总结

主要的疑惑在于怎么去找到交换最小的次数。那我们一定要开天眼的，用已知的有序去与无序的比较，因为不在自己位置上的数，至少要经过一次交换才能回到自己的位置上，交换完后这个数就固定下再也不管了, 这样就能保证交换的次数是最小的次数。