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):
"123""132""213""231""312""321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
1 class Solution { 2 public: 3 string getPermutation(int n, int k) { 4 string result; 5 bool used[10]; 6 memset(used, false, 10); 7 int base[10]; 8 base[1] = 1; 9 for (int i = 2; i <= n; ++i) { 10 base[i] = base[i - 1] * i; 11 } 12 --k; 13 for (int i = 0; i < n; ++i) { 14 int p = k / base[n - 1 - i]; 15 for (int j = 1; j <= n; ++j) { 16 if (!used[j] && p-- == 0) { 17 result.push_back(‘0‘ + j); 18 used[j] = true; 19 break; 20 } 21 } 22 k %= base[n - 1 - i]; 23 } 24 return result; 25 } 26 };
n个数组的全排列中，以1开头的个数(n-1)!个，同样以2..n开头的个数有(n-1)!个，这样根据(k-1)/[(n-1)!]可知第一个数是多少，依次类推...
【Leetcode】Permutation Sequence,布布扣,bubuko.com
【Leetcode】Permutation Sequence
原文：http://www.cnblogs.com/dengeven/p/3607992.html
