iframe-proxy | Sunbelt Computer Software

Repository navigation

// Time: O(n^2)

// Space: O(n)

class Solution {

public:

string getPermutation(int n, int k) {

vector<int> nums;

int total = 1;

for (int i = 1; i <= n; ++i) {

nums.emplace_back(i);

total *= i;

}

// Cantor Ordering:

// Construct the k-th permutation with a list of n numbers

// Idea: group all permutations according to their first number (so n groups, each of

// (n - 1)! numbers), find the group where the k-th permutation belongs, remove the common

// first number from the list and append it to the resulting string, and iteratively

// construct the (((k - 1) % (n - 1)!) + 1)-th permutation with the remaining n-1 numbers

int group = total;

stringstream permutation;

while (n > 0) {

group /= n;

int idx = (k - 1) / group;

permutation << nums[idx];

nums.erase(nums.begin() + idx);

k = (k - 1) % group + 1;

--n;

}

return permutation.str();

}

};