[每日一题] 第四题：圆圈中最后剩下的数字

DRose 的个人博客 / 11 / 0 / 创建于 3年前 / 更新于 3年前

题目描述

0，1,……，n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是 2、0、4、1，因此最后剩下的数字是 3。

题解

方法一：公式法

代码

class Solution {
    public int lastRemaining(int n, int m) {
        int ans = 0;
        // 最后一轮剩下2个人，所以从2开始反推
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % i;
        }
        return ans;
    }
}

复杂度

时间复杂度：O(n)，需要求解的函数值有 n 个。
空间复杂度：O(1)，只使用常数个变量。

个人理解

数学解法：感觉就是不是我们的常规方法，一个特定的公式，反正就用这个公式能算出来。
公式：f(N,M) = (f(N-1,M) + M) % N，其中：
1. N 表示 N 个数
2. M 表示上面删除的第 m 个数字
3. f(N,M) 表示 N 个数，每次删除第 M 个数的时候，最终剩下的数的编号
4. f(N-1,M) 表示，N-1 个数，每次删除第 M 个数的时候，最终剩下的数的编号
理解记住：我也很好奇怎么得出这个公式是怎么来的，但是我觉得理解记住这个公式更重要，知道可以用这种递推公式得出也很重要。
手动模拟：我们来手动模拟一下上述问题求解过程。
1. 【0，1，2，3，4】。第一轮我们删除了第三个数字，也就是 2。下一个开头数字为 3。
2. 【3，4，0，1】。第二轮我们删除了第三个数字，也就是 0。下一个开头数字为 1。
3. 【1，3，4】。第三轮我们删除第三个数字，也就是 4.下一个开头数字为 1。
4. 【1，3，1】。第四轮我们删除第三个数字，也就是 1。因为只剩下两个数字，为了构成个环，我们在后面补上一个 1，此时剩下最后一个数据 3，最终结果为 3。
公式验证：我们再用上面的公式来验证一下公式是否正确。注意：该公式得出来的结果是数字的下标（把上述看成一个数组 array）
1. f(1,3)：只有 1 个数，那这个数就是最终结果，它的下标位置为 0，即 f(1,3)=0。
2. f(2,3) =（f(1,3)+3）% 2 = 1：有 2 个数，剩下的数的下标位置为 1，即 f(2,3)=1。
3. f(3,3) =（f(2,3)+3）% 3 = 1：有 3 个数，剩下的数的下标位置为 1，即 f(3,3)=2。
4. f(4,3) =（f(3,3)+3）% 4 = 0：有 4 个数，剩下的数的下标位置为 0，即 f(4,3)=0。
5. f(5,3) =（f(4,3)+3）% 5 = 3：有 5 个数，剩下的数的下标位置为 3，即 f(5,3)=3。
公式的出来的结果同上面手动模拟的出来的结果一致，数组 array[3]=3。我们再理解一下为什么这个公式得出来的是数组的下标。
问题一：假设我们已经知道了有 5 个数字的时候，最终留下来的数字是下标位置为 3 的数字，那下一轮只有 4 个数字的时候，留下来的数字的下标位置是多少?
1. 其实，第一轮删除第 3 个数字的时候，3 后面的数字都向前移动 3 位，最终留下来的数字也向前移动 3 位，也就是 0。
问题二：假设我们知道了 4 个数字的时候，最终留下来的数字的下标为 0，那么当数字有 5 个的时候，最终留下来的数字的下标是多少？
1. 这个过程可以看做是上一个过程的逆过程，大家都往后移动 3 位，所以 f(5,3) =（f(4,3)+3) = 3。不过有可能数组越界，所以模上当前的数字的个数。即：f(5,3) =（f(4,3)+3）% 5 = 3。
问题三：现在有 N 个数字，删除第 M 个数字，应该怎么移动？
1. 每删除一个数字，下一个数字成为第一个数字，相当于把整个数组前移 M 位。若已知 N-1 个数字的时候，最终留下来的数字的下标为 f(N-1,M)，则当数字个数为 N 个的时候，最终留下来的数字就要后移 M 位，即 f(N,M) = f(N-1,M) + M。因为有可能数组越界，所以要模上 N。即：f(N,M) = (f(N-1,M) + M) % N。
这可以解释了为什么这个公式求的是最终留下来的数字的下标，因为删除数字会引起数字下标位置的移动。
为什么递推可以？环状填充理解。这个理解还是很可以，无论删除多少个，俩环最终剩下的部分都长得一样，所以可以转为递推公式来理解。且满足上述递推公式。
递推公式的起点和终点？ 首先初始位置为 0，然后从第二轮开始，所以要 i=2，到第 N 轮，所以要 i<=N。每次执行 result=(result+m)%i。其中 m 是要删除的数，i 为当的轮数。

来源

来源：力扣（LeetCode）

链接：leetcode-cn.com/problems/yuan-quan...

参考文档

约瑟夫环——公式法（递推公式）

leetcode 简单

本作品采用《CC 协议》，转载必须注明作者和本文链接

DRose

版主 484 声望

暂无个人描述~

0 人点赞

讨论数量: 0

(=￣ω￣=)··· 暂无内容！

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

[每日一题] 第四题：圆圈中最后剩下的数字

题目描述

题解

方法一：公式法

代码

复杂度

个人理解

来源

参考文档

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

[每日一题] 第四题：圆圈中最后剩下的数字

题目描述

题解

方法一：公式法

代码

复杂度

个人理解

来源

参考文档

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录