剑指 Offer ！！62. 圆圈中最后剩下的数字（约瑟夫环问题）

剑指 Offer 62. 圆圈中最后剩下的数字
简单
818
相关企业
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：

输入: n = 5, m = 3
输出: 3
示例 2：

输入: n = 10, m = 17
输出: 2

一个很通俗易懂的题解
这个题解的缺点在于，推导过程有些粗糙……从一个案例直接退出递推公式。
优点在于，通俗易懂。
左程云的书（《程序员代码面试指南》第2版）上有一个还算规范的推导。

// 解法一：模拟法
   public int lastRemaining1(int n, int m) {
        ArrayList<Integer> list = new ArrayList();
        for(int i=0;i<n;i++){
            list.add(i);
        }
        int idx=0;

        while(n>1){
            idx = (idx+m-1)%n;// the one ready to be killed
            list.remove(idx);
            n--;
        }
        // now,n=1 means only one person is left
        return list.get(0);
    }

// 解法二：从最后一轮（幸存者的下标ans为0）开始，向前推，每次推上一轮这个幸存者的下标是什么，直到圈子长度为n为止，返回此时幸存者的下标
    public int lastRemaining(int n, int m) {
        int ans=0;
        for(int i=2;i<=n;i++){
        // 上一轮圈子的长度为i
            ans = (ans+m)%i;
         // 此时，ans为 在上一轮圈子中幸存者的下标
        }
        return ans;
    }