Leetcode and Lintcode

Permutation Sequence

Problem:

Given n and k, return the k-th permutation sequence.

Example
For n = 3, all permutations are listed as follows:

"123"
"132"
"213"
"231"
"312"
"321"
If k = 4, the fourth permutation is "231"

Note
n will be between 1 and 9 inclusive.

Challenge
O(n*k) in time complexity is easy, can you do it in O(n^2) or less?

Leetcode link
Lintcode link

My Solution:

The most intuitive way is calling nextPermuation method for k times. It takes O(k * n);
Assume there are n non-repeated numbers,whose k-th permuation is a1,a2,a3, …, an.
For each increassing of a1, there are (n-1)! possibilities for a2 to an. So a1 = k / (n-1)!;
Similarly we can get the following as following:

k_2 = k % (n-1)!;
a_2 = k_2 / (n-2)!;
   ...
k_{n-1} = k_{n-2} / 2!;
a_{n-1} = k-{n-1} / 1!;
a_n = 1;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*************************************************************************
	> File Name: PermuationSequence.java
	> Author: Yao Zhang 
	> Mail: psyyz10@163.com 
	> Created Time: Thu 12 Nov 15:14:13 2015
 ************************************************************************/

public class PermuationSequence{
    public String getPermutation(int n, int k) {
        StringBuilder builder = new StringBuilder();
        int factor = 1; 
        for (int i = 1; i < n; i++){                                                                                            
            factor *= i;
        }               
                        
        boolean[] used = new boolean[n];
        k = k - 1; // note  k should minus 1
        for (int i = 0; i < n; i++){
            int index = k / factor; 
            k = k % factor;         
                        
            for (int j = 0; j < n; j++){
                if (!used[j]){      
                    if (index == 0){
                       builder.append(String.valueOf(j + 1)) ; 
                       used[j] = true;
                       break;       
                    } else{         
                        index--;    
                    }   
                }       
            }           
                        
            if (n - 1 != i)         
                factor /= (n - 1 - i);
        }               
                        
        return builder.toString();  
    }
}