#60medium
code1：
class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> num = new ArrayList<>();
        for (int i = 1; i <= n; i++) num.add(i);
        int[] factorial = new int[n];
        factorial[0] = 1;
        for (int i = 1; i < n; i++) factorial[i] = i * factorial[i-1];
        n--;
        StringBuilder res = new StringBuilder();
        while (n >= 0){
            int t = factorial[n];
            int loc = (int) (Math.ceil((double) k / (double) t)) - 1;
            if (loc == -1) loc = num.size() - 1;
            res.append(num.get(loc));
            num.remove(loc);
            k %= t;
            n--;
        }
        return res.toString();
    }
}

code2：
class Solution {
    public String getPermutation(int n, int k) {
        StringBuilder sb = new StringBuilder();
        //阶乘数组
        int[] factorials = new int[n];
        //注意0和1的阶乘为1
        factorials[0] = 1;
        //阶乘值为当前值乘前一个阶乘值
        for(int i = 1; i < n;i++){
            factorials[i] = i * factorials[i-1];
        }
        //list存储“数字”，因此remove后依旧有序，无需排序。
        //这保证了我们只要知道需要获取值的偏移量就可以得到对应的值。
        List<Character> nums = new ArrayList<>();
        for(int i = 1; i <= n;i++){
            nums.add((char)(i+48));
        }
        int index;
        //将题目的人类习惯奇数改为list内部下标计数。
        k--;
        //最差情况下从第一位一直运算到第n-1位，最后一位便是剩下的。
        for(int j = 1;j < n;j++){
            int factorial = factorials[n-j];
            //获取该位“数字”在list内的下标
            index = k / factorial;
            k = k % factorial;
            //将这一位“数字”加进来后从list内部删除该“数字”
            sb.append(nums.get(index));
            nums.remove(index);
            //如果此时不再有相对偏移量，退出循环。
            if(k == 0){
                break;
            }
        }
        //如果最差情况，此时将最后一位加进来，
        //如果中途因为刚好匹配、没有偏移量而退出则按序将剩余“数字”加进来。
        while (nums.size()>0){
            sb.append(nums.get(0));
            nums.remove(0);
        }
        return sb.toString();
    }
}

code3:
class Solution {
    public String getPermutation(int n, int k) {
        StringBuilder res=new StringBuilder();
        String num="123456789";
        int[] f=new int[n];
        for(int i=0;i<n;i++) f[i]=1;
        for(int i=1;i<n;i++)
            f[i]=f[i-1]*i;
        --k;
        for(int i=n;i>=1;--i){
            int j=k/f[i-1];
            k %=f[i-1];
            res.append(num.charAt(j));
            num=num.replace(num.substring(j,j+1),"");
        }
        return res.toString();
    }
}