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.
We can conclude a pattern by obeservation.
[x1, x2, x3, .., xn]
If we fix x1, then number of permutations is (n - 1)!
If we fix x1 and x2, then number of permutations is (n - 2)!
Following this thinking way, we can solve this problem by finding xi iteratively.
We also need a visited array here to note which element has been used.
1 public class Solution { 2 public String getPermutation(int n, int k) { 3 StringBuilder sb = new StringBuilder(n); 4 if (n < 1 || n > 9) 5 return sb.toString(); 6 int factorial = 1; 7 for (int i = 1; i <= n; i++) { 8 factorial *= i; 9 } 10 if (k > factorial || k < 1) 11 return sb.toString(); 12 boolean[] visited = new boolean[n]; 13 14 int num = n; 15 int start = 1; 16 while (num > 0) { 17 factorial /= num; 18 start += (k / factorial); 19 if (k % factorial == 0) 20 start -= 1; 21 int index = 0; 22 for (int i = 1; i <= n; i++) { 23 // Find the right index 24 if (!visited[i - 1]) 25 index++; 26 if (index == start) { 27 sb.append(i); 28 visited[i - 1] = true; 29 break; 30 } 31 } 32 k = k - (start - 1) * factorial; 33 start = 1; 34 num--; 35 } 36 return sb.toString(); 37 } 38 }
原文：http://www.cnblogs.com/ireneyanglan/p/4888763.html