LeetCode如何求圓圈中最后剩下的數(shù)字

題目描述

0,1,,n-1 這 n 個數(shù)字排成一個圓圈，從數(shù)字 0 開始，每次從這個圓圈里刪除第 m 個數(shù)字。求出這個圓圈里剩下的最后一個數(shù)字。

例如，0、1、2、3、4 這 5 個數(shù)字組成一個圓圈，從數(shù)字 0 開始每次刪除第 3 個數(shù)字，則刪除的前 4 個數(shù)字依次是 2、0、4、1，因此最后剩下的數(shù)字是 3。

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

題目樣例

示例

• 輸入: n = 5, m = 3

• 輸出: 3

• 輸入: n = 10, m = 17

• 輸出: 2

題目思考

1. n 個數(shù)字和 n-1 個數(shù)字最后剩下的數(shù)字有什么關系嗎?

解決方案

思路

• 一個比較容易想到的思路是暴力法, 即使用數(shù)組模擬整個過程: 記錄當前起點, 求要移除的下個數(shù)字的下標, 并從原列表中移除它. 但這樣時間復雜度達到了 O(N^2), 因為移除元素也需要 O(N) 時間
• 而改用雙端鏈表的話則為 O(MN), 因為雖然移除變?yōu)榱?O(1), 但每次定位下一個要移除的數(shù)字下標時不能像數(shù)組那樣 O(1) 時間定位, 而是需要 O(M) 時間來遍歷到下個移除的位置
• 那有什么方法可以做到更小的時間復雜度呢?
• 如果我們能從 n-1 個數(shù)字的結(jié)果, 推導出 n 個數(shù)字的結(jié)果, 那就可以一次遍歷 O(N) 時間搞定
• 所以嘗試動態(tài)規(guī)劃的思路, 設                          dp[n, m]是 n 個數(shù)字時每次刪除第 m 個數(shù)字的最后剩下數(shù)字的下標
• 第一次刪除時, 刪除數(shù)字的下標 i 為                          (m-1)%n, 而其下一個下標 i+1 為下一次刪除的起點
• 此時將新的起點 i+1 映射為下標 0, 自然 i+2 就對應下標 1, ... 到最后原下標 i 就對應映射下標 n-2. 這樣就轉(zhuǎn)換成了 n-1 個數(shù)字時每次刪除第 m 個數(shù)字的情況
• 顯然映射下標 x 與原下標 y 的關系是                          y = (x+i+1)%n, 而 i 為                          (m-1)%n, 所以可以進一步得到                          y = (x+m)%n
• 下標映射之后, 此時總共有 n-1 個數(shù)字, 最終剩余的數(shù)字就是                          dp[n-1,m], 這個是映射下標, 根據(jù)上面的下標轉(zhuǎn)換關系, 反推出原下標就是                          (dp[n-1,m]+m)%n
• 而不管是第一次刪除還是第二次刪除, 其最終剩余的數(shù)字只能是同一個,                          所以dp[n, m] = (dp[n-1,m]+m)%n, 這就是最核心的狀態(tài)轉(zhuǎn)移方程
• 觀察可以發(fā)現(xiàn), 每個 dp 值只和前一個 dp 值相關, 所以我們可以使用一個變量來節(jié)省空間, 然后從小到大遍歷到 n 即可
• 而 dp 初始值為 n=1 的情況, 此時最后剩余的數(shù)字顯然只能是 0

復雜度

• 時間復雜度 O(N): 只需要遍歷到 N
• 空間復雜度 O(1): 只使用了常數(shù)個變量

代碼

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