class Solution {
    //对于n, 有n!种排列, 则可以通过计算k 与 n! 的倍数来判断当前的数字, 比如n=3, k=3, 此时第一个数字肯定为2, 因为第一个数字为1的排列种数为2个
    public String getPermutation(int n, int k) {
        int[] nums = new int[n-1];
        List<Integer> list = new LinkedList<>();
        if(n > 1){
            nums[0] = 1;
        }
        for (int i = 1; i < n-1; i++){ //存储n!, 用于判断
            nums[i] = nums[i-1]*(i+1);
        }
        for(int i = 0; i < n; i++){
            list.add(i+1);
        }
        StringBuilder sb = new StringBuilder();
        k--;
        for(int i = n-1; i > 0;i--){
            int index = k/ nums[i-1];
            k = k % nums[i-1];
            sb.append(list.get(index));
            list.remove(index);
        }
        sb.append(list.get(0));

        return sb.toString();
    }
}