LeetCode 面试题62. 圆圈中最后剩下的数字 详细题解

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

难度 简单
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

题解：

这是LeetCode在2020.3.30的打卡题，同时也是一个面试题。这里是0到n-1，一共n个数，然后每次删除第m个数，删除之后就以刚刚删除点的下一个点作为第一个点，继续删除这个圈中的最后一个点，题目要求我们找出最后剩下的数字是哪一个也就是最后剩余的那个数的位置。
很多小伙伴一看到题目很容易的想到去模拟这个过程，创建一个vector，然后赋值0~n-1，使用一个循环进行删除，但是由于这里删除也是O(n)的，所以整体上时间效率就是O(n^2)了，所以很容易的超时。
我们这里可以不需要实际的模拟，我们可以使用递归的解决这个问题，只需要求解出上一次删除的点就可，不需要实际去删除，这样我们的时间效率就是O(n)，会稍微好一点。相对与每一个当前节点，我们只需要知道当前的起点即可求解出当前需要删除的结点。
下面上代码：

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