剑指Offer - 面试题62. 圆圈中最后剩下的数字（约瑟夫环 递推公式）

1. 题目

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）
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
还有 5727. 找出游戏的获胜者 https://leetcode-cn.com/problems/find-the-winner-of-the-circular-game/

我的博客 链表： 约瑟夫环问题

2. 解题

类似题目：LeetCode 390. 消除游戏（类似约瑟夫环，找映射规律）

2.1 数组模拟超时

极限数据下，超时了

class Solution { public:int lastRemaining(int n, int m) {vector<int> num(n);int i;for(i = 0; i < n; i++)num[i] = i;i = 0;while(num.size() != 1){i = (i+m-1)%num.size();num.erase(num.begin()+i);//不断的删除}return num[0];} };

2.2 公式法

参考别人的解法

• $f(people,num)$ 表示在有people个人时，报数为num，胜利的人的位置
• people = 1 时， pos = 0
• $pos=f(people,num)=(f(people-1,num)+num)\%people$

class Solution { public:int lastRemaining(int n, int m) {int pos = 0;//1个人时for(int i = 2; i <= n; i++){ //i表示人数pos = (pos+m)%i;}return pos;} };

总结

以上是生活随笔为你收集整理的剑指Offer - 面试题62. 圆圈中最后剩下的数字（约瑟夫环 递推公式）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。