MediumRating 1412
1823. Find the Winner of the Circular Game
arraymathrecursionqueuesimulation
解題說明
Find the Winner of the Circular Game
題目描述：n 個朋友圍坐成一圈（編號 1 到 n），從第 1 個人開始每次數 k 個人，被數到的人離開。重複直到剩下一個人。求最後留下的人的編號。（即約瑟夫問題）
解題思路：這是經典的約瑟夫問題（Josephus Problem）。有數學遞推公式：設 f(n, k) 為 n 個人中最後存活者的索引（0-based），則 f(1, k) = 0，f(n, k) = (f(n-1, k) + k) % n。最終答案為 f(n, k) + 1（轉為 1-based）。可用迭代或遞迴實現，時間 O(n)，空間 O(1)。
C++ 解法
複雜度分析
時間複雜度：O(n) — 單層迴圈從 2 到 n。
空間複雜度：O(1) — 只需一個變數追蹤存活者位置。
虛擬碼
1. Set survivor = 0 (base case: 1 person, 0-indexed position) 2. For i = 2 to n: a. survivor = (survivor + k) % i 3. Return survivor + 1 (convert to 1-based)
其他解法
佇列模擬：用佇列模擬整個過程：每次將前 k-1 個人移到隊尾，第 k 個人移除。時間 O(nk)，直觀但較慢。
鏈結串列模擬：用環形鏈結串列，每次數 k 步後刪除節點。時間 O(nk)，但不需要移動元素。適合理解問題但效率不及數學解法。
延伸思考
- 若 k 很大（遠大於 n），約瑟夫公式如何加速計算？
- 若要知道每個人被淘汰的順序，如何記錄？
- 若改為反方向計數（逆時針），結果如何變化？