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. 圆圈中最后剩下的数字（约瑟夫环 递推公式）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。