算法

(数学) $O(n^2)$

注意到，以任何一个数字$i$为开头的可能的排列都是有$(n-1)!$种的可能性的。题目让我们找第$k$大的，所以我们可以从最高位开始一个一个地去排除，也就是每次执行$k / (n-1)!$的操作。比如$k=3$，那我们最多可以减去一个$(n-1)!$，也就是$2$个，那么它只能排除掉以$1$为开头的排序，然后我们可以确定我们需要找的在以$2$为开头的排列中。

Java 代码

class Solution {
    public String getPermutation(int n, int k) {
        int[] f = new int[n];
        f[0] = 1;
        for (int i = 1; i < n; ++i) {
            f[i] = i * f[i - 1];
        }
        List<Integer> num = new ArrayList();
        for (int i = 1; i <= n; ++i) {
            num.add(i);
        }
        k--;
        StringBuilder res = new StringBuilder();
        for (int i = n - 1; i >= 0; --i) {
            int idx = k / f[i];
            res.append(num.get(idx));
            num.remove(idx);
            k %= f[i];
        } 
        return res.toString();
    }
}