Solution

• 模拟法

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        if (n <= 0 || m < 0) return -1;
        // 利用数组模拟环删除过程
        vector<int> nums(n, 0);
        int index = -1, step = 0, count = n;
        while (count >0) {
            index++;    // 指向上一个被删除对象的下一个元素
            if (index >= n) index = 0;  // 模拟环
            if (nums[index] == -1) continue;    // 跳过被删除的元素
            step++;    // 记录已经走过的
            if (step == m) {    // 找到待删除对象
                nums[index] = -1;
                step = 0;
                count--;
            }
        }
        return index;    // 返回最后一个被设为 -1 的元素
    }
};

• 约瑟夫环，利用公式

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        // 约瑟夫环
        if (n <= 0 || m < 0) return -1;
        int res = 0;
        for (int i = 2; i <= n; ++i) {
            res = (res + m) % i;
        }
        return res;
    }
};