60. Permutation Sequence

leetcode 
class Solution {
public:
    string getPermutation(int n, int k)
    {
        // 計算每個數字的階乘的結果，將其保存在 factorials 中。
        vector<int> factorials(n, 1);

        // 使用一個 loop 從 1 開始，計算階層
        // factorials 會是 [1, 1, 2, 6, 24, 120, 720, 5040, 40320]
        //                [0!, 1!, 2!, 3!, 4!, 5!, 6!, 7!, 8!, 9!]
        for (int i = 1; i < n; ++i)
        {
            factorials[i] = factorials[i - 1] * i;
        }

        // k - 1，因為 index 是從 0 開始的
        --k;

        string res;
        string num = "123456789";

        // 從 n 開始遞減到 1
        for (int i = n; i >= 1; --i)
        {
            // j 代表當前數字在結果中的位置
            int j = k / factorials[i - 1];

            // 取餘數
            k %= factorials[i - 1];

            // 從 num 中取出第 j 個數字，推到 res 中
            res.push_back(num[j]);
            // 從 num 消去已經使用過的數字
            num.erase(j, 1);
        }
        return res;
    }
};
  • T: O(N2)O(N^2)
  • S: O(N)O(N)