Permutation Sequence

Source

lintcode: Permutation Sequence

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?

Java

class Solution {
    /**
      * @param n: n
      * @param k: the kth permutation
      * @return: return the k-th permutation
      */
    public String getPermutation(int n, int k) {
        List<Integer> num = new LinkedList<Integer>();
        for (int i=1; i<=n; i++) num.add(i);

        //caculate factorial
        int[] fact = new int[n];
        fact[0]=1;
        for(int i=1; i<n; i++){
            fact[i] = i*fact[i-1];
        }

        k--;
        StringBuilder sb = new StringBuilder();
        for(int i=n; i>0; i--){
            int ind = k/fact[i-1];
            k = k%fact[i-1];
            sb.append(num.get(ind));
            num.remove(ind);
        }
        return sb.toString();      
    }
}

Reference

Permutation Sequence