LeetCode 60 Permutation Sequence：階乘進制直接定位第 k 個排列

給定 n 和 k，直接求 1..n 的全排列中第 k 個（1-based）。利用階乘進制特性，每位可直接計算，無需生成前 k-1 個。

核心洞察

固定首位時，剩餘 n-1 位有 (n-1)! 種排列。故第 k 個排列的首位索引為 (k-1) / (n-1)!（0-based）。取出該數字後，對餘數遞推處理下一位。

算法步驟

1. 預計算階乘 fact[i] = i!。
2. 維護可用數字列表 nums = [1..n]。
3. k-- 轉為 0-based。
4. 對位置 i = n-1 到 0：idx = k / fact[i]，選 nums[idx] 加入結果，從列表移除，k %= fact[i]。

參考代碼

public String getPermutation(int n, int k) {
    List nums = new ArrayList<>();
    int fact = 1;
    for (int i = 1; i <= n; i++) {
        nums.add(i);
        if (i < n) fact *= i; // (n-1)!
    }
    k--; // 0-based
    StringBuilder sb = new StringBuilder();
    for (int i = n - 1; i >= 0; i--) {
        int idx = k / fact;
        sb.append(nums.remove(idx));
        k %= fact;
        if (i > 0) fact /= i;
    }
    return sb.toString();
}

複雜度

時間 O(n²)（ArrayList.remove 為 O(n)），空間 O(n)。若用 Fenwick Tree 或 Segment Tree 維護可用數字可優化至 O(n log n)，但 n≤9 時 O(n²) 足夠。