🔗 🟡 1823. Find the Winner of the Circular Game 1412

tags: `Weekly Contest 236` `陣列(Array)` `模擬(Simulation)` `佇列(Queue)` `遞迴(Recursion)` `數學(Math)`

題意

有 $n$ 個人正在玩一個遊戲。所有人坐成一圈，按照 順時針順序 從 $1$ 到 $n$ 編號。從第 $i$ 個人順時針移動一位會到達第 $(i+1)$ 個人的位置，其中 $1 \leq i < n$ ，而從第 $n$ 個人順時針移動一位會回到第 $1$ 個人的位置。

遊戲規則如下：

從第 $1$ 個人所在位置開始。
沿著順時針方向數 $k$ 個人，計數時需要包含起始時的那位，被數到的人會離開圓圈並視為輸掉遊戲。
如果圓圈中仍然有不止一個人，從剛剛輸掉的人的 順時針下一位 開始，回到步驟 $2$ 繼續執行。
否則，圓圈中最後一個人獲勝。

給定參與遊戲的人數 $n$ 和整數 $k$ ，請返回遊戲的獲勝者編號。

思路

方法一：模擬(Simulation) + 佇列(Queue)

根據題意，最直觀的方式就是使用佇列(Queue) 來模擬(Simulation) 遊戲過程。在每一輪遊戲中，我們從佇列的前端取出 $k-1$ 個人，並將他們依次加到佇列的尾部，最後將第 $k$ 個人，也就是佇列前端的人移出。重複這個過程直到佇列中只剩下一個人，即為獲勝者。

複雜度分析

時間複雜度： $\mathcal{O}(n \cdot k)$ ，每一輪遊戲需要移動 $k-1$ 個人，並移除 $1$ 個人，總共需要進行 $n-1$ 輪。
空間複雜度： $\mathcal{O}(n)$ ，使用了一個佇列來存儲所有參與遊戲的人。

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        q = deque(range(1, n+1))
        while len(q) > 1:
            for _ in range(k-1):
                q.append(q.popleft())
            q.popleft()
        return q[0]

class Solution {
public:
    int findTheWinner(int n, int k) {
        queue<int> q;
        for (int i = 1; i <= n; i++) q.push(i);
        while (q.size() > 1) {
            for (int i = 0; i < k-1; i++) {
                q.push(q.front());
                q.pop();
            }
            q.pop();
        }
        return q.front();
    }
};

方法二：約瑟夫問題(Josephus Problem) + 遞迴(Recursion)

事實上，這個問題是經典的數學問題，稱為約瑟夫問題(Josephus Problem) ，可以使用遞迴的方式來解決這個問題。

令 $J(n, k)$ 表示有 $n$ 個人參與遊戲，每次數 $k$ 個人，最後獲勝者的位置，此處先以 $0-based$ 來表示位置。根據遞迴的思路，我們可以通過以下公式來計算 $J(n, k)$ ：

若 $n = 1$ ，則獲勝者的位置為 $0$ ；
若 $n > 1$ ，則獲勝者的位置可以通過上一次遊戲的獲勝者位置和 $k$ 的關係推算出來： $J(n, k) = (J(n-1, k) + k) \bmod n$ 。具體推導過程可以參考參考資料中的連結。

由於我們的數字是從 $1$ 到 $n$ 而不是從 $0$ 開始，因此需要在取模之前先減去 $1$ ，最後再加上 $1$ 。修改後的公式如下：

$J(1, k) = 1$ ；
$J(n, k) = ((J(n-1, k) + k - 1) \bmod n) + 1$ 。

根據 $J(n, k)$ 的公式，使用遞迴的方式即可求解出最終的答案。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，需要遞迴 $n$ 次來求解最終的答案。
空間複雜度： $\mathcal{O}(n)$ ，遞迴過程中使用的堆疊空間。

1
2
3

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        return 1 if n == 1 else (self.findTheWinner(n-1, k) + k - 1) % n + 1

class Solution {
public:
    int findTheWinner(int n, int k) {
        return (n == 1) ? 1 : (findTheWinner(n-1, k) + k - 1) % n + 1;
    }
};

方法三：約瑟夫問題(Josephus Problem) + 迭代(Iteration)

同樣地，根據 $J(n, k)$ 的公式，我們可以使用迭代(Iteration) 的方式來求解最終的答案。

初始化答案 $ans = 1$ ，從 $i = 2$ 開始遍歷 $[2, n]$ ，每次更新答案 $ans = (ans + k - 1) \bmod i + 1$ 。

最後返回 $ans$ 即可。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，需要遍歷 $n-1$ 次來求解最終的答案。
空間複雜度： $\mathcal{O}(1)$ 。

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        ans = 1
        for i in range(2, n+1):
            ans = (ans + k - 1) % i + 1
        return ans

class Solution {
public:
    int findTheWinner(int n, int k) {
        int ans = 1;
        for (int i = 2; i <= n; i++) {
            ans = (ans + k - 1) % i + 1;
        }
        return ans;
    }
};