1823. Find the Winner of the Circular Game

這道題目描述了一個遊戲:

1. n 個玩家圍成一圈,編號從 1 到 n。
2. 從第 1 號玩家開始,順時針數 k 個人。
3. 被數到的玩家退出遊戲。
4. 剩下的玩家繼續遊戲,從被淘汰玩家的下一位開始重複步驟 2-3。
5. 最後剩下的玩家獲勝。

題目要求我們找出獲勝者的編號。

解決這個問題的方法有幾種:

1. 模擬法:直接模擬遊戲過程,使用一個數列或鏈表來表示玩家,並按照規則刪除玩家直到剩下最後一個。
2. 約瑟夫環問題:這實際上是一個經典的約瑟夫環問題。可以使用遞歸或迭代的方式求解。
3. 數學解法:有一個數學公式可以直接計算出結果,但理解起來可能較為複雜。

• Recursion

class Solution {
public:
    int findTheWinner(int n, int k)
    {
        return helper(n, k) + 1;
    }

    int helper(int n, int k)
    {
        if (n == 1) return 0;
        return (helper(n - 1, k) + k) % n;
    }
};

• T: $O(n)$

• S: $O(n)$

• Iteration

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

• T: $O(n)$
• S: $O(1)$