Permutation Sequence -- LeetCode

原题链接: http://oj.leetcode.com/problems/permutation-sequence/
这道题目算法上没有什么特别的，更像是一道找规律的数学题目。我们知道，n个数的permutation总共有n阶乘个，基于这个性质我们可以得到某一位对应的数字是哪一个。思路是这样的，比如当前长度是n，我们知道每个相同的起始元素对应(n-1)!个permutation，也就是(n-1)!个permutation后会换一个起始元素。因此，只要当前的k进行(n-1)!取余，得到的数字就是当前剩余数组的index，如此就可以得到对应的元素。如此递推直到数组中没有元素结束。实现中我们要维护一个数组来记录当前的元素，每次得到一个元素加入结果数组，然后从剩余数组中移除，因此空间复杂度是O(n)。时间上总共需要n个回合，而每次删除元素如果是用数组需要O(n),所以总共是O(n^2)。这里如果不移除元素也需要对元素做标记，所以要判断第一个还是个线性的操作。代码如下：

public String getPermutation(int n, int k) {
    if(n<=0)
        return "";
    k--;
    StringBuilder res = new StringBuilder();
    int factorial = 1;
    ArrayList<Integer> nums = new ArrayList<Integer>();
    for(int i=2;i<n;i++)
    {
        factorial *= i;
    }
    for(int i=1;i<=n;i++)
    {
        nums.add(i);
    }
    int round = n-1;
    while(round>=0)
    {
        int index = k/factorial;
        k %= factorial;
        res.append(nums.get(index));
        nums.remove(index);
        if(round>0)
            factorial /= round;
        round--;
    }
    return res.toString();
}

上面代码还有有个小细节，就是一开始把k--，目的是让下标从0开始，这样下标就是从0到n-1，不用考虑n时去取余，更好地跟数组下标匹配。如果有朋友有更好的思路来实现线性的时间复杂度，欢迎指教哈，可以留言或者发邮件到linhuanmars@gmail.com给我。