LeetCode如何求圆圈中最后剩下的数字

题目描述

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

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

• 1 <= n <= 10^5
• 1 <= m <= 10^6

题目样例

示例

• 输入: n = 5, m = 3

• 输出: 3

• 输入: n = 10, m = 17

• 输出: 2

题目思考

1. n 个数字和 n-1 个数字最后剩下的数字有什么关系吗?

解决方案

思路

• 一个比较容易想到的思路是暴力法, 即使用数组模拟整个过程: 记录当前起点, 求要移除的下个数字的下标, 并从原列表中移除它. 但这样时间复杂度达到了 O(N^2), 因为移除元素也需要 O(N) 时间
• 而改用双端链表的话则为 O(MN), 因为虽然移除变为了 O(1), 但每次定位下一个要移除的数字下标时不能像数组那样 O(1) 时间定位, 而是需要 O(M) 时间来遍历到下个移除的位置
• 那有什么方法可以做到更小的时间复杂度呢?
• 如果我们能从 n-1 个数字的结果, 推导出 n 个数字的结果, 那就可以一次遍历 O(N) 时间搞定
• 所以尝试动态规划的思路, 设
                           dp[n, m]是 n 个数字时每次删除第 m 个数字的最后剩下数字的下标
• 第一次删除时, 删除数字的下标 i 为
                           (m-1)%n, 而其下一个下标 i+1 为下一次删除的起点
• 此时将新的起点 i+1 映射为下标 0, 自然 i+2 就对应下标 1, … 到最后原下标 i 就对应映射下标 n-2. 这样就转换成了 n-1 个数字时每次删除第 m 个数字的情况
• 显然映射下标 x 与原下标 y 的关系是
                           y = (x+i+1)%n, 而 i 为
                           (m-1)%n, 所以可以进一步得到
                           y = (x+m)%n
• 下标映射之后, 此时总共有 n-1 个数字, 最终剩余的数字就是
                           dp[n-1,m], 这个是映射下标, 根据上面的下标转换关系, 反推出原下标就是
                           (dp[n-1,m]+m)%n
• 而不管是第一次删除还是第二次删除, 其最终剩余的数字只能是同一个,
                           所以dp[n, m] = (dp[n-1,m]+m)%n, 这就是最核心的状态转移方程
• 观察可以发现, 每个 dp 值只和前一个 dp 值相关, 所以我们可以使用一个变量来节省空间, 然后从小到大遍历到 n 即可
• 而 dp 初始值为 n=1 的情况, 此时最后剩余的数字显然只能是 0

复杂度

• 时间复杂度 O(N): 只需要遍历到 N
• 空间复杂度 O(1): 只使用了常数个变量

代码

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        # 初始dp[1,m]为0
        dp = 0
        for x in range(2, n + 1):
            # 对应公式dp[x,m] = (dp[x-1,m] + m) % x
            dp = (dp + m) % x
        return dp