Skip to main content

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)O(n)

  • S: O(n)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)O(n)
  • S: O(1)O(1)