方法：约瑟夫环 + 倒推
解题思路
- 假设我们最好剩余的数字是 \(N\)。
- 执行完 "删除第三个元素" 的操作后，\(N\) 在新数组中的位置 \(P\) 的意义是什么？它表示，在新数组中，\(N\) 前面有还有 \(P\) 个元素。那么，在当前数组中，\(N\) 前面一定有 \(P+3\) 个元素。 明白了这一点即可开始倒推。
- 最后一轮：当前有 \(1\) 个元素。\(N\) 的位置是 \(0\)；
- 倒数第 \(2\) 轮：当前有 \(2\) 个元素。已知在执行完 "删除第三个元素" 后，\(N\) 在新数组中的位置是 \(0\)。则说明在本轮中 \(N\) 前面有 \(0+3=3\) 个元素，所以 \(N\) 的位置是 \(3\)，然而本轮只有 \(2\) 个元素，所以 \(N\) 的实际位置是 \((0+3)%2=1\)；
- 倒数第 \(3\) 轮：当前有 \(3\) 个元素。已知在执行完 "删除第三个元素" 后，\(N\) 在新数组中的位置是 \(1\)。说明此刻，\(N\) 前面有 \(1+3=4\) 个元素，所以 \(N\) 的位置是 \(4\)。而当前数组只有 \(3\) 个元素，故实际位置是 \((1+3)%3=1\)；
- ...
代码
class Solution {
public:
int lastRemaining(int n, int m) {
int x = 0;
for (int i = 2; i <= n; i ++ ) {
x = (x + m) % i;
}
return x;
}
};
复杂度分析
时间复杂度：\(O(n)\);
空间复杂度：\(O(1)\)。