置換環(huán)可以得到數(shù)組排序（可以指定排序方式）所需交換的最小次數(shù)。其的思想是：將每個(gè)節(jié)點(diǎn)指向其排序后應(yīng)該存放的位置，最終首位相接形成一個(gè)環(huán)，那么數(shù)組排序所需的最小交換次數(shù)為數(shù)組長(zhǎng)度-環(huán)的數(shù)量。

包含自環(huán)

置換環(huán)-01.jpg

代碼為：

public int template(int[] source, int[] target) {
    int len = source.length;
    Map<Integer, Integer> map = new HashMap<>(); // 存儲(chǔ)目標(biāo)排序每個(gè)元素的位置
    boolean[] flag = new boolean[len]; // 標(biāo)識(shí)當(dāng)前字符串是否已經(jīng)訪問過
    for (int i = 0; i < len; i++) map.put(target[i], i);

    int loop = 0; // 環(huán)的數(shù)量
    for (int i = 0; i < len; i++) {
        if (flag[i]) continue;
        int cur = source[i];
        while (!flag[cur]) {
            flag[cur] = true;
            cur = source[map.get(cur)];
        }
        loop++;
    }
    return len - loop;
}

參考鏈接：

1. 【二叉樹層序遍歷 + 置換環(huán) + Java】逐層排序二叉樹所需的最少操作數(shù)目
2. BFS + 置換環(huán) + 離散化