首页 > 代码库 > leetcode. Permutation Sequence

leetcode. 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.

 1 string getPermutation(int n, int k)  2     { 3         string s; 4         if (k <= 0 || n <= 0) 5             return s; 6              7         int *array = new int[n], *fact = new int[n + 1], select, i, j; 8         fact[0] = 1; 9         for (i = 0; i < n; i++)10         {   11             array[i] = 1 + i;12             fact[i + 1] = fact[i] * (i + 1);13         }14         15         for (i = 0; i < n; i++)16         {17             select = (k - 1) / fact[n - i - 1];18             k = k - select * fact[n - i - 1];19             s += array[select];20             for (j = select; j < n - 1; j++)21                 array[j] = array[j + 1];22         }23         24         delete[] array;25         return s;26     }

 

leetcode. Permutation Sequence