使用布尔来识别/隔离数组的元素（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