圆圈中最后剩下的数字

链接：剑指 Offer 62. 圆圈中最后剩下的数字
比较好理解的方法：

class Solution {
  public int lastRemaining(int n, int m) {
    List<Integer> list=new ArrayList<>();
    for(int i=0;i<n;i++){
        list.add(i);
    }
    int index=0;
    while(n>1){
        index=(index+m-1)%n;
        list.remove(index);
        n--;
    }
    return list.get(0);
  }
}

有一个数学方法：
约瑟夫环——公式法（递推公式）
可以推导得到公式
f(1)=0
f(2)=(f(1)+m)%2=1
f(3)=(f(2)+m)%3=1
f(4)=(f(3)+m)%4=0
f(5)=(f(4)+m)%5=3
每次去掉哪一个，相当于把数组中所有数字往前移动m位删掉最后一个
所以最后活下来的那个数字，每一轮都在被往前移动m位
因为最后只剩它一个的时候，index=0
倒推得到最开始的下标

class Solution {
  public int lastRemaining(int n, int m) {
    int index=0;
    for(int i=2;i<=n;i++){
        index=(index+m)%i;
    }
    return index;
  }
}