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

题目描述

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),只使用常数个变量。

个人理解

  1. 数学解法:感觉就是不是我们的常规方法,一个特定的公式,反正就用这个公式能算出来。

  2. 公式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 个数的时候,最终剩下的数的编号

  3. 理解记住:我也很好奇怎么得出这个公式是怎么来的,但是我觉得理解记住这个公式更重要,知道可以用这种递推公式得出也很重要。

  4. 手动模拟:我们来手动模拟一下上述问题求解过程。

    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

  5. 公式验证:我们再用上面的公式来验证一下公式是否正确。注意:该公式得出来的结果是数字的下标(把上述看成一个数组 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

  6. 公式的出来的结果同上面手动模拟的出来的结果一致,数组 array[3]=3。我们再理解一下为什么这个公式得出来的是数组的下标。

  7. 问题一:假设我们已经知道了有 5 个数字的时候,最终留下来的数字是下标位置为 3 的数字,那下一轮只有 4 个数字的时候,留下来的数字的下标位置是多少?

    1. 其实,第一轮删除第 3 个数字的时候,3 后面的数字都向前移动 3 位,最终留下来的数字也向前移动 3 位,也就是 0
  8. 问题二:假设我们知道了 4 个数字的时候,最终留下来的数字的下标为 0,那么当数字有 5 个的时候,最终留下来的数字的下标是多少?

    1. 这个过程可以看做是上一个过程的逆过程,大家都往后移动 3 位,所以 f(5,3) =(f(4,3)+3) = 3。不过有可能数组越界,所以模上当前的数字的个数。即:f(5,3) =(f(4,3)+3)% 5 = 3
  9. 问题三:现在有 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
  10. 这可以解释了为什么这个公式求的是最终留下来的数字的下标,因为删除数字会引起数字下标位置的移动。

  11. 为什么递推可以?环状填充理解。这个理解还是很可以,无论删除多少个,俩环最终剩下的部分都长得一样,所以可以转为递推公式来理解。且满足上述递推公式。

  12. 递推公式的起点和终点? 首先初始位置为 0,然后从第二轮开始,所以要 i=2,到第 N 轮,所以要 i<=N。每次执行 result=(result+m)%i。其中 m 是要删除的数,i 为当的轮数。

来源

来源:力扣(LeetCode)

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

参考文档

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!