100个小球，拼成一个圆，从0开始，顺时针方向每隔两个球就取走一个，问最后剩哪个球？

Question

问题：100个小球，拼成一个圆，从0开始，顺时针方向每隔两个球就取走一个，问最后剩哪个球？
初步解题思路：定义一个数组存0-99。借助临时的集合。约瑟夫环
用Java实现

Answer 1

数组够了，不用集合，数组当链表用

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

        System.out.println(main.getLast(100,2));
    }

    //我这里删的是2 4 6 8，这样的,假设要删的是1 3 5 7 那就把idx改成cnt-1
    public int getLast(int cnt,int step){
       int[] arr = new int[cnt];
       for(int i = 0; i < cnt-1; i++){
           arr[i]=i+1;
       }
       arr[cnt-1]=0;

       int last = cnt;
       int idx = 0;//假设第一次要删的是2，idx=0；第一次删的是1，idx=cnt-1;
       while(last>1){
            for(int i = 0; i < step-1; i++){
                idx = arr[idx];
            }
            //当前指向的是拿走的前一个球,指向下一个
           //System.out.println(arr[idx]);
           arr[idx]=arr[arr[idx]];
           --last;
       }
       return arr[idx];
    }
}