Permutation Sequence

06/28/2016 Backtracking Math

Question

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

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

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

Given and , return the permutation sequence.

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


Solution

Result: Accepted Time: 0 ms

Here should be some explanations.

class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        string nums = "123456789";
        int f[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880},i,j;
        for (i = n,--k; i >= 1; --i) {
            j = k / f[i - 1];
            k %= f[i - 1];
            res.push_back(nums[j]);
            nums.erase(nums.begin() + j);
        }
        return res;
    }
};

Complexity Analytics

  • Time Complexity:
  • Space Complexity: