java算法题小朋友做游戏

Question

n 个小朋友正在做一个游戏，每个人要分享一个自己的小秘密。每个小朋友都有一个 1 到 n 的编号，编号不重复

Answer 1

其实就是检查循环情况，出现循环就不必继续了

public class Main {
    public static void main(String[] args) {
        Main main = new Main();

        Scanner sc = new Scanner(System.in);
        int step = sc.nextInt();
        int[] arr = new int[step];
        for(int i = 0; i < step; i++){
            arr[i] = sc.nextInt();
        }
        System.out.println(main.findPerson(arr));
    }

    private int findPerson(int [] arr){
        int n = arr.length;
        boolean[] checked = new boolean[n];

        int ans = 0;
        for(int i = 0; i < n; i++){
            if(checked[i])continue;
            ++ans;
            int idx = i;
            while(!checked[idx]){
                checked[idx]=true;
                idx = arr[idx]-1;//位置是索引+1
            }
        }
        return ans;
    }
}