60. Permutation Sequence

class Solution {
    public String getPermutation(int n, int k) {
        int[] factorial = new int[n];
        factorial[0] = 1; // 0 的阶乘为 1
        for (int i = 1; i < factorial.length; i++) {
            factorial[i] = i * factorial[i - 1];
        }

        List<Integer> numList = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            numList.add(i);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = n - 1; i >= 0; i--) {
            int index = k / factorial[i];
            if (k % factorial[i] == 0) {
                // 能够整除
                index--;
            }
            sb.append(numList.remove(index));
            k -= index * factorial[i];
        }

        return sb.toString();
    }
}

Reference

60. Permutation Sequence