Skip to main content

60. Permutation Sequence

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)