使用布爾來識別/隔離數組的元素（java）

Question

我是一位通過codefights.org等編碼和學習的新手。我偶然發現了這個問題：

======

找到一個給定的置換週期數。

例

對於置換= [1，3,2，6,4，5]，輸出應該是 permutationCycles（置換）= 3 *

int permutationCycles(int[] permutation) { 

    boolean[] inCycle = new boolean[permutation.length]; 
    int result = 0; 

    for (int i = 0; i < permutation.length; i++) { 
    if (!inCycle[i]) { 
     int position = i; 
     while (!inCycle[position]) { 
     inCycle[position] = true; 
     position = //...// ; 
     } 
     result++; 
    } 
    } 

    return result; 
} 

任務是用正確的代碼替換//...//。我可以用我自己的方式編碼，但不使用布爾數組。我不明白的是如何將布爾數組inCycle連接到排列數組。有人可以向我解釋這裏的if循環是什麼意思嗎？提前致謝。

Answer 1

如果我理解這個問題，應該是

position = permutation[position] - 1; 

這使您可以將當前週期的下一個元素。我使用permutation[position] - 1而不是permutation[position]，因爲示例中的索引從1開始，而Java數組基於0。

布爾數組用於標記哪些元素已經訪問過（因此屬於某個已經計算的週期）。

對於置換[1, 3, 2, 6, 4, 5]，執行是這樣的：

i == 0 
    position = 0 
    position = permutation [0] - 1 = 0 -> this closes the first cycle 
i == 1 
    position = 1 
    position = permutation [1] - 1 = 2 
    position = permutation [2] - 1 = 1 -> this closes the 2nd cycle 
i == 2 already in cycle 
i == 3 
    position = 3 
    position = permutation [3] - 1 = 5 
    position = permutation [5] - 1 = 4 
    position = permutation [4] - 1 = 3 -> this closes the 3rd cycle 
i == 4 already in cycle 
i == 5 already in cycle