Permutation Sequence leetcode

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.

题解：from http://www.cnblogs.com/springfor/p/3896201.html

发现数学规律。

首先先捋捋这道题要干啥，给了我们n还有k，在数列 1，2，3，... , n构建的全排列中，返回第k个排列。

题目告诉我们：对于n个数可以有n!种排列；那么n-1个数就有(n-1)!种排列。

那么对于n位数来说，如果除去最高位不看，后面的n-1位就有 (n-1)!种排列。

所以，还是对于n位数来说，每一个不同的最高位数，后面可以拼接(n-1)!种排列。

所以你就可以看成是按照每组(n-1)!个这样分组。 

利用 k/(n-1)! 可以取得最高位在数列中的index。这样第k个排列的最高位就能从数列中的index位取得，此时还要把这个数从数列中删除。

然后，新的k就可以有k%(n-1)!获得。循环n次即可。

 同时，为了可以跟数组坐标对其，令k先--。

时间上总共需要n个回合，而每次删除元素如果是用数组需要O(n),所以总共是O(n^2)

public class Solution {
    public String getPermutation(int n, int k) {
        k = k-1;//为了使k的值对应num数组的坐标
        ArrayList<Integer> num = new ArrayList<Integer>();
        for (int i = 1 ; i <= n; i++) {
            num.add(i);
        }
        int factor = 1;
        for (int i = 2; i < n; i++) {
            factor *= i;
        }
        StringBuilder tem = new StringBuilder();
        for (int time = n-1; time >= 0; time--) {
            int index = k / factor;
            tem.append(num.get(index));
            num.remove(num.get(index));//因为只能出现一次 所以用过就抹去
            k = k % factor;
            if (time != 0) {
                factor = factor / time;
            }
        }
        return tem.toString();
    }
}