Leetcode 面试题62.圆圈中最后剩下的数字【C++】

地址：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

解题思路

这题最容易想到的思路肯定是模拟真实的逐个删除的场景了，也就是暴力解，但是我并没有上来就这么做，我觉得这题肯定就不是让这么做的，暴力解存在挺大的问题，很傻，要遍历 n 次，逻辑也不是很好写。

自己想却真就想不出来好办法，后来看了官方题解，确实比暴力解好很多吧，但是实在不是我能想出来的，甚至有一个步骤（ f(n, m) 和 f(n - 1, m) 之间的关系）我看了题解也花了不少时间菜弄明白。具体的思路还是看官方题解吧，挺难用文字描述清楚的，这个题更偏向于数学问题，用数学的方法解体就简单很多。

同时官方题解分别用递归和迭代做了这个题，其实都是一个思路，理论上说递归更符合人的思路，但是 n 越大就要递归越深使用大量的栈空间，所以迭代是更好的办法，并且只需要一个变量保存相关数据，空间复杂度O(1)。

代码

递归：

class Solution {
public:
    int lastRemaining(int n, int m) {
        return f(n, m);
    }
    
    int f(int n, int m) {
        if (n == 1)
            return 0;
        int x = f(n - 1, m);
        return (m + x) % n;
    }
};

迭代：

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