題目描述

有個遊戲是這樣的：⾸先，讓 n 個⼩朋友們圍成⼀個⼤圈，⼩朋友們的編號是0~n-1。然後，隨機指定⼀個數 m ，讓編號為0的⼩朋友開始報數。每次喊到 m-1 的那個⼩朋友要出列唱⾸歌，然後可以在禮品箱中任意的挑選禮物，並且不再回到圈中，從他的下⼀個⼩朋友開始，繼續 0... m-1報數....這樣下去....直到剩下最後⼀個⼩朋友，可以不⽤表演，並且拿到⽜客禮品，請你試着想下，哪個⼩朋友會得到這份禮品呢？

示例
輸⼊：5,3
輸出：2

思路及解答

數組模擬

通過布爾數組標記小朋友的出局狀態

public class Solution {

    public int lastRemaining(int n, int m) {
        if (n <= 0 || m <= 0) return -1;
        
        boolean[] out = new boolean[n]; // 標記是否出局
        int count = n;                  // 剩餘人數
        int index = 0;                  // 當前報數位置
        int step = 0;                   // 報數計數器
        
        while (count > 1) {
            // 如果當前小朋友未出局，參與報數
            if (!out[index]) {
                step++;
                // 報到m-1的小朋友出局
                if (step == m) {
                    out[index] = true;  // 標記出局
                    count--;            // 剩餘人數減1
                    step = 0;           // 重置計數器
                }
            }
            // 移動到下一個位置（循環）
            index = (index + 1) % n;
        }
        
        // 找到最後一個未出局的小朋友
        for (int i = 0; i < n; i++) {
            if (!out[i]) {
                return i;
            }
        }
        return -1;
    }
}

• 時間複雜度：O(n×m)，最壞情況下每個小朋友都需要報數m次
• 空間複雜度：O(n)，需要長度為n的布爾數組

循環鏈表

使用循環鏈表模擬小朋友圍成的圈，將小朋友存入鏈表，循環刪除第m個元素

public class Solution {

    public int lastRemaining(int n, int m) {
        if (n <= 0 || m <= 0) return -1;
        
        List<Integer> list = new LinkedList<>();
        // 初始化鏈表，存入所有小朋友編號
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        
        int index = 0; // 當前指針位置
        
        while (list.size() > 1) {
            // 計算要刪除的位置：(當前索引 + m-1) % 當前大小
            index = (index + m - 1) % list.size();
            list.remove(index);
            // 刪除後index自動指向下一個元素，不需要移動
        }
        
        return list.get(0);
    }
}

• 時間複雜度：O(n×m)，需要遍歷鏈表進行刪除操作
• 空間複雜度：O(n)，需要存儲n個節點

數學歸納法（推薦）

分析每次被刪除的數字規律，直接計算出最後的數字，不需要模擬

F(N,M) = ( F(N−1,M) + M ) % N

遞推公式的推導過程：

1. 第一次刪除：從0開始報數，刪除第(m-1)%n個小朋友

2. 重新編號：刪除後，從第m%n個小朋友開始重新編號：

   • 舊編號：m%n, m%n+1, ..., n-1, 0, 1, ..., m%n-1
   • 新編號：0, 1, 2, ..., n-2
3. 映射關係：新編號x對應的舊編號為(x + m) % n

示例驗證（n=5, m=3）：

原始編號: 0, 1, 2, 3, 4
第一次刪除編號2 → 剩餘: 0, 1, 3, 4
重新編號: 3→0, 4→1, 0→2, 1→3
f(5,3) = (f(4,3) + 3) % 5

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if (n <= 0 || m <= 0) {
            return -1;
        }
        int result = 0;
        for (int i = 2; i <= n; i++) {
            result = (result + m) % n;
        }
        return result;
    }
}

• 時間複雜度：O(n)，需要n次遞歸調用
• 空間複雜度：O(n)，遞歸調用棧深度

迭代優化

將遞歸轉為迭代，避免棧溢出風險，是生產環境的最佳選擇

public class Solution {

    public int lastRemaining(int n, int m) {
        if (n <= 0 || m <= 0) return -1;
        
        int result = 0; // f(1, m) = 0
        
        // 從2個人情況開始，逐步計算到n個人
        for (int i = 2; i <= n; i++) {
            result = (result + m) % i;
        }
        
        return result;
    }
}

• 時間複雜度：O(n)，只需一次循環
• 空間複雜度：O(1)，只使用常數空間