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時去取餘，更好地跟數組下标比對。如果有朋友有更好的思路來實作線性的時間複雜度，歡迎指教哈，可以留言或者發郵件到 [email protected] 給我。