剑指offer-62-圆圈中最后剩下的数字

题目

思路

1. 暴力解的话太简单了…看看有没有其他方法
2. 最后只剩下一个元素，假设这个最后存活的元素为 num, 这个元素最终的的下标一定是0 （因为最后只剩这一个元素）
3. 那么此时我们拿到了最后一轮的下标，所以看是否可以推出上一轮次中这个num的下标。
4. 以
   为例
5. 首先在3前面补充m个数字，变回到了第四轮的状况，想要求3上一轮的下标，这个下标肯定是小于上一轮元素个数的（n,n-1,n-2…1），所以对其取模。
6. 所以答案是**(当前index + m) % 上一轮剩余数字的个数**

代码

    public int lastRemaining(int n, int m) {
        int ans = 0;
        // 最后一轮剩下2个人，所以从2开始反推
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % i;
        }
        return ans;
    }
1
2
3
4
5
6
7
8