剑指offer 70. 圆圈中最后剩下的数字

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：剑指offer系列题解
📝原题地址：题目地址
📣专栏定位：为找工作的小伙伴整理常考算法题解，祝大家都能成功上岸！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

题目描述

0,1,…,n−1 这 n 个数字 (n>0) 排成一个圆圈，从数字 0 开始每次从这个圆圈里删除第 m 个数字。

求出这个圆圈里剩下的最后一个数字。

数据范围

1≤n,m≤4000

样例

输入：n=5 , m=3

输出：3
1
2
3

方法一：递推 O(n)

这道题通过找规律可以得到下面这个公式：

旧编号 = (新编号 + m) % n

这么一看可能会比较懵，光看公式会不太理解，我们直接上例子，在计算过程中理解这个公式，假设 n = 5 且 m = 3 ，来模拟一下计算的过程。

第一步： 从数字 0 开始数三个，即删除数字 2 。

第二步： 从数字 3 开始数三个，即删除数字 0 。

第三步： 从数字 1 开始数三个，即删除数字 4 。

第四步： 从数字 1 开始数三个，即删除数字 1 。

第五步： 现在只剩下一个数字，直接返回数字 3 即可。

你可能还会比较疑惑，上面这些跟那个公式有什么关系吗？

重点来了，可以看到我每个图中都给每个数字进行重新编号，而最后答案数字 3 的编号为 0 ，因为只有一个数字了。那么我们该如何从这个新的编号得到数字 3 最一开始的编号呢。

我们一开始只知道 n 和 m ，并不知道哪个才是最后剩下的数字，但是一定可以知道的是该数字的新编号一定是 0 ，现在我们开始往回推！

第一步： 数字 3 的新编号为 0 ，那么其上一轮的编号就为 (0 + 3) % 2 = 1 。

第二步： 数字 3 的新编号为 1 ，那么其上一轮的编号就为 (1 + 3) % 3 = 1 。

第三步： 数字 3 的新编号为 1 ，那么其上一轮的编号就为 (1 + 3) % 4 = 0 。

第四步： 数字 3 的新编号为 0 ，那么其上一轮的编号就为 (0 + 3) % 5 = 3 。

这时得到的编号 3 就是答案 3 最开始的位置，所以我们可以得到开头的那个公式：

旧编号 = (新编号 + m) % n

先去递归到最后一轮，从已知的编号 0 往回推，就可以得到最终的答案。

class Solution {
public:
    int lastRemaining(int n, int m) {
        if (n == 1)    return 0;
        return (lastRemaining(n - 1, m) + m) % n;
    }
};
1
2
3
4
5
6
7

欢迎大家在评论区交流~