问题

约瑟夫环。

算法：找规律+反向模拟

最后一个剩下的数在数组中的索引为0，我们考虑：最初的时候它在数组中的索引是多少？

模拟整个过程可知，每轮的第1个数字是上一轮的第m+1个数字，因此可以反向推导最后一个数上一轮的索引：(0 + m) % 2（上一轮有2个数因此%2）

又推导最后一个数上上轮的索引：((0+m)%2+m)%3（上上轮有3个数）

…

最后到有n个数停止，则那个索引就是我们要找的数

时间复杂度

$O(N)$

代码

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