62. 圆圈中最后剩下的数字

1. 描述

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

2. 例子

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

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

3. 限制

• 1 <= n <= $10^5$
• 1 <= m <= $10^6$

4. 题解

时间复杂度: O(n)
空间复杂度: O(1)

我们定义方程 $f(n, m)$，其意义为当数组有 n 个数字时，我们每次去除第 m 个数字，最后剩下的数字下标
所以可以看出来 $f(n, m)$ 就是我们想要的结果
当然，我们是不可能现在就知道这个方程的结果的，但是我们知道 $f(1, m)$ 的结果一定是零，因为我们要求的是最后剩下的数字坐标
而仅有一个数字时，那它自然是最后剩下的数字，而仅有一个数字时，它的坐标也必定是零
所以说，我们现在知道了 $f(1, m)$，同时我们的目标是 $f(n, m)$，所以我们需要做的是找到方程之间的递推关系
其递推关系为 $f(n, m) = (f(n - 1, m) + m) \% n$
由此，我们可以完成代码

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

		return resultIndex;
    }
};