LeetCode Permutation Sequence：第 k 個排列的數學解法

題目描述

給定整數 n 和 k，集合 [1, 2, 3, ..., n] 共有 n! 種唯一排列。若將所有排列按字典序列出並標記，例如 n = 3 時序列為：「123」、「132」、「213」、「231」、「312」、「321」。請返回第 k 個排列序列。注意：n 介於 1 到 9 之間。

解題思路

直觀做法是透過遞歸窮舉所有排列，或從 "123...n" 反覆呼叫 nextPermutation 產生下一個排列，但這會導致超時 (TLE)。因為我們只需要第 k 個排列，不必生成前面所有排列。利用數學方法，可直接根據 n 和 k 依序決定第 1 位到第 n 位的數字。

核心觀察：固定第一位數字後，剩餘 n-1 個數字有 (n-1)! 種排列。因此第一位數字的索引為 k / (n-1)!（將 k 減 1 改為 0-based 索引）。選出該數字後，從可用數字集合中移除，更新 k 為 k % (n-1)!，然後用 (n-2)! 繼續決定第二位，以此類推。

詳細代碼 (Java)

public String getPermutation_math(int n, int k) {
    k = k - 1; // 改為 0-based 索引
    List<Integer> list = new LinkedList<>();
    StringBuilder resultBuilder = new StringBuilder();
    int factorial = 1;
    for (int i = 1; i <= n; i++) {
        list.add(i);
        factorial *= i;
    }
    factorial /= n; // 現在是 (n-1)!
    
    for (int i = 1; i <= n; i++) {
        if (i == n) { // 最後一位直接取剩餘唯一數字
            resultBuilder.append(list.get(0));
            break;
        }
        int index = k / factorial;
        resultBuilder.append(list.get(index));
        list.remove(index);
        k = k % factorial;
        factorial /= (n - i); // 更新為 (n-i-1)!
    }
    return resultBuilder.toString();
}

補充：nextPermutation 實現與超時示例

（超時代碼以及 getNextPermutation 函數實現）

// 取得 "123...n" 的第 k 個全排列（會超時）
public String getPermutation(int n, int k) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++) a[i] = i + 1;
    for (int step = 1; step < k; step++) {
        // 尋找第一個逆序點
        int i = n - 1;
        while (i > 0 && a[i-1] >= a[i]) i--;
        if (i == 0) break; // 已是最後一個排列
        // 找右側比 a[i-1] 大的最小值
        int j = n - 1;
        while (a[j] <= a[i-1]) j--;
        // 交換
        int tmp = a[i-1]; a[i-1] = a[j]; a[j] = tmp;
        // 將 i 之後的序列逆序
        for (int l = i, r = n - 1; l < r; l++, r--) {
            tmp = a[l]; a[l] = a[r]; a[r] = tmp;
        }
    }
    StringBuilder sb = new StringBuilder();
    for (int num : a) sb.append(num);
    return sb.toString();
}