圆圈中最后剩下的数字 shuitang

## 题目

来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof

0,1,,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

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

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

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

限制: 1 <= n <= 10^5 1 <= m <= 10^6

求解

这是数学中著名的约瑟夫环问题。由于数据量给了限制,所以不方便使用模拟方法来求解,只能找一种时间复杂度为 O(n) 的算法来求解。 思路是递归。注意到当数是 n 个的时候,删除一个就变成 n-1 了,具有潜在的递归求解的思路。我们假设 f(n,m) 表示从 0 开始每次数 m 个数到最后得到的数,或者换句话说 f(n,m) 表示最后得到的数偏移起始位置多少个位置。开始时,删除的数显然是 n%m, 删除完之后就是 n-1 个数了。假如我们知道 f(n-1,m) 的值,即最后的数离起始位置差 x = f(n-1,m) 个数,那么 f(n,m) 最后删的数离起始位置(即 0)为: n%m + f(n-1,m)这么多,对应的数为 (n%m + f(n-1,m))%m。 而起始 n = 1时,显然 f(1,m) = 0, 所以代码就很简单了:

class Solution {
public:
    int lastRemaining(int n, int m) {
        if(n == 1) return 0;

        return (lastRemaining(n-1,m) +  m )%n;
    }
};