leetcode Permutation Sequence

Permutation Sequence

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.

   Discuss

   
   
   

   Three problems:

   1. overly dependent on next_permutation, TLE

   2. --k. If k%a! == b, so the bth character should be brought forward from the rear a elements.

   3. If the length is n, n - 1 adjustments are enough. So i = n instead of n - 1

   for (i = n - 1; i >= 1; --i) {

   
   

   class Solution {
    public:
     int factorial[10];
     string getPermutation(int n, int k) {
       string res = "";
       int i, j, tmp;
       vector
       
         pos;
       factorial[0] = 1;
       for (i = 1; i <= n; ++i) {
         factorial[i] = factorial[i - 1] * i;
         res.push_back('0' + i);
       }
       --k;
       for (i = n - 1; i >= 1; --i) {
         pos.push_back(k / factorial[i]);
         k = k % factorial[i];
       }
       for (i = 0; i < pos.size(); ++i) {
         tmp = res[i + pos[i]];
         for (j = pos[i]; j >= 1; --j)
           res[i + j] = res[i + j - 1];
         res[i] = tmp;
       }
       
       return res;
     }
   };