Permutation Sequence

Desicription

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

  1. “123”
  2. “132”
  3. “213”
  4. “231”
  5. “312”
  6. “321”

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        vector<int> nums(n), f(n);
        for (int i=0; i<n; i++) nums[i]=i+1;
        f[0]=1;
        for (int i=1; i<n; i++) f[i]=f[i-1]*i;
        
        k--;
        for (int i=n-1; i>=0; i--) {
            int j=k/f[i];
            res+=nums[j]+'0';
            nums.erase(nums.begin()+j);
            k%=f[i];
        }
        return res;
     }
};