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.

Permutation Sequence
 1 public class Solution {
 2     public String getPermutation(int n, int k) {
 3         int num[] = new int [n];
 4         int permu = 1;
 5         for(int i=0;i<n;i++){
 6             num[i]=i+1;
 7             permu *= i+1;
 8         }
 9         k--;        
10         StringBuilder sb =new StringBuilder();
11         for(int i=0;i<n;i++){
12             permu /=n-i;
13             int selected = k/permu;
14             sb.append(num[selected]);
15             k %= permu;
16             for(int j=selected+1;j<n;j++){
17                 num[j-1] = num[j];
18             }
19         }
20         return sb.toString();
21     }
22 }
View Code

Permutation Sequence

上一篇:Pow(x, n)


下一篇:Anagrams