leetcode 60

这道题其实可以通过给的n值知道一共有n!种组合，通过给的k值可以知道开头第一位数字是多少，举例来说，比如n的值是4，可以知道一共有24中组合方式（1234,1243,...,4321)，如果k是14的话（写代码的时候k要减一操作），可以知道如果n是3的时候有6种组合，14/6=2可以知道，第一位的数字是3，这样还剩下124在后三位，然后用14-26=2，可以知道新的k的值；
此时n就变成了三位数的排列组合，如果要判断第二位数，此时用2/2=1，也就是说，第二位是1；
然后再次更新k=2-12 = 0，也就是说后面是按从小到大的顺序，2，4，得到3124是第14个数，代码如下：

public static String getPermutation(int n, int k) {
        if (k <= 0) return null;
        if (n <= 0) return null;
        int num = 1;
        List<Integer> numbers = new ArrayList<>();
        int[] fac = new int[n+1];
        fac[0] = 1;
        String str = "";
        //计算不同的n，组合的数量
        for (int i = 1; i <= n; i++) {
            num *= i;
            fac[i] = num;//{1,1,2,6,24,...}
//            System.out.println(fac[i]);
        }
        for (int i = 1; i <= n; i++) {
            numbers.add(i);
        }
        k--;
        for (int i = 1; i <= n; i++) {
            int first = k/fac[n-i];//计算是几开头的数
            str = str + Integer.toString(numbers.get(first));
//            System.out.println(str);
            numbers.remove(first);
            k = k - first * fac[n-i];
        }
        return str;
    }