算法23 Permutation Sequence

题目：
该集合共包含n！独特的排列。[1,2,3,…,n]
通过按顺序列出和标记所有的排列，
我们得到以下序列（即n = 3）：
"123"
"132"
"213"
"231"
"312"
"321"
给定n和k，返回第k 个排列序列。
注：鉴于n将在1和9之间。

思路：
从阶乘的基本规律我们可以看到对于数字n来说，从1到n的每个数字开头的排列有(n - 1)!个。就像前面这样，以1, 2, 3, 4分别开头的排列它们每个都是有6个。因此对于我们的数字k来说，它对(n - 1)!相除得到的值就是当前所在的列，这个列索引就是我们所要确定的第一个元素。而它对(n - 1)!取余数，得到的数字就是当前剩余数组的index，因此也就可以得到对应的元素。在具体的实现里，我们需要用一个数组来保存数字1到n，每次找到对应索引的时候，从数组里把这个元素取出来加入到结果数组中，并将它从原来的数组里删除。
以前面的数字４为例，假设我们要取第8个排列所在的位置，因为索引从0开始，所以相当于求索引位置为7的那个排列。按照前面的推导过程，首先我们要求它首个位置的元素，因为3! = 6，　7 / 6 = 1。所以我们要从索引１里面找，也就是排列数组里的数字２。这个时候我们去掉数字２，排列数组里的元素是[1, 3, 4]，我们目前的结果数组里的数字是２。这个时候按照同样的方式来推导，我们确定了是在第二列。我们要找的下一个元素的index是7 % 6 = 1。而这时候要求的下一级的阶乘则是2! = 2。1 / 2 = 0，所以取数字１。目标数组现在是[2, 1]，排列数组里剩余元素为[3, 4]。这个时候再求下一个的元素。因为这一级的阶乘是1! = 1，而当前1 / 1 = 1，所以我们需要找到索引位置是1。所以要取的下一个元素就是4。此时结果数组里包含有数字[2, 1, 3]。而此时1 % 1 = 0，下一个要计算的当前值就是0。不过对于最后这个元素可以不用计算了，直接取出来放到最后的结果数组里就是我们期望的结果。

代码：

public class Solution {
    public String getPermutation(int n, int k) {
        int fact = 1;
        for (int i = 2; i < n; i++) {
            fact *= i;
        }
        List<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            nums.add(i);
        }
        int rank = k - 1;
        StringBuilder ans = new StringBuilder();
        for (int i = n - 1; i > 0; --i) {
            int index = rank / fact;
            ans.append(nums.remove(index));
            rank %= fact;
            fact /= i;
        }
        ans.append(nums.remove(0));
        return ans.toString();
    }
}

时间复杂度O(n),空间复杂度O(n)