Leetcode初學——第K個排列

題目：

分析：

這道題我第一個想到的方法是回溯法，因為我們之前做過一道全排列的題，這個題就隻是取全排列中的第K個情況

為了友善減少時間的損耗，我還進行了剪枝，計算出第K個情況後就不再計算

class Solution {
    private List<String> res=new ArrayList<String>();
    public String getPermutation(int n, int k) {
        List<String> list=new ArrayList<String>();
        for(int i=1;i<=n;i++){
            list.add(i+"");
        }
        helpToGetPermutation(k,list,new ArrayList<String>());
        return res.get(k-1);
    }
    protected void helpToGetPermutation(int k,List<String>list,List<String> temp ){
        if(res.size()==k)
            return;
        if(list.size()==0){
            String s="";
            for(String str:temp)
                s+=str;
            res.add(s);
            return;
        }

        for(int i=0;i<list.size();i++){
            String str=list.get(i);
            temp.add(str);
            list.remove(str);
            helpToGetPermutation(k,list,temp);
            temp.remove(str);
            list.add(i,str);
        }

    }

}
           

很可惜的是，上面這個代碼逾時了，即使剪枝，依然逾時

是以我開始思考，有沒有更好的方法呢？

當n=3時

123

132

213

231

312

321

有6種情況

當n=2時

12

21

有2種情況

我們可以發現，n的全排列個數=n*（n-1）的全排列個數

當n=4,k=15時

确定第一位:

            k = 14(從0開始計數)

            index = k / (n-1)! = 2, 說明第15個數的第一位是3

            更新k

            k = k - index*(n-1)! = 2

        确定第二位:

            k = 2

            index = k / (n-2)! = 1, 說明第15個數的第二位是2

            更新k

            k = k - index*(n-2)! = 0

        确定第三位:

            k = 0

            index = k / (n-3)! = 0, 說明第15個數的第三位是1

            更新k

            k = k - index*(n-3)! = 0

        确定第四位:

            k = 0

            index = k / (n-4)! = 0, 說明第15個數的第四位是4

        最終确定n=4時第15個數為3214

代碼：

class Solution {
    public String getPermutation(int n, int k) {
        String res="";
        List<String> list=new ArrayList<String>();
        for(int i=1;i<=n;i++){
            list.add(i+"");
        }
        k--;
        while(res.length()!=n){
            int flag=1;
            for(int i=1;i<=list.size()-1;i++)
                flag*=i;
            int index=k/flag;
            res+=list.get(index);
            list.remove(index);
            k=k%flag;
        }
        return res;
    }
}
           

結果：