LeetcodeDaily | 1579. 圆圈中最后剩下的数字

忘是亡心i 2023-07-19 12:08 9阅读 0赞

## 题目 ##

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

## 思路 ##

本来一开始，就觉得又规律可循，就一直在用数组推导，但是这样会超时。看了题解才发现这是个递归问题，讲的是“约瑟夫环”。  
可以用倒推的方式来理解，其中因为是从0-n的所以返回数字就相当于是返回位置。

约瑟夫环的公式是：  
![在这里插入图片描述][20200330220249990.png]

所以可以用递归：

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

也可以直接用循环

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;
        }
    };

**参考：**

*  [LeetCode官方题解][LeetCode]
 *  [约瑟夫环——公式法（递推公式）][Link 1]

[20200330220249990.png]: /images/20230528/99466c08c85c42b5b81656f4fc944d1b.png
[LeetCode]: https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-by-lee/
[Link 1]: https://blog.csdn.net/u011500062/article/details/72855826