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 nums = new ArrayList();
    for(int i=2;i=0)
    {
        int index = k/factorial;
        k %= factorial;
        res.append(nums.get(index));
        nums.remove(index);
        if(round>0)
            factorial /= round;
        round--;
    }
    return res.toString();
}