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;
    }
}
           

结果：