分析

• 本题的考点：数学。

• 对于c++而言，可以使用next_permutation，计算量为$n! \times n$，最大为$9! \times 9 = 3,265,920$，可以通过，考试肯定用这种做法。

• 下面讲解另一种做法：计数法。

• 对于n，我们要求第k大的小的数，我们可以依次考虑1~n这些位置应该放入哪个数字，从第一个位置开始考虑，如果放入1的话，则后面还有n-1个位置，一共有(n-1)!种方案，比较k和(n-1)!的大小，如果k > (n-1)!，说明第k小的数必定不可能是1开头的数字。之后将k更新为k-(n-1)!，考虑第一个位置放入2，直到找到第一个位置放置的数字，使得$k \le (n-1)!$，则该数字就是第一位应该放的数字。

• 依次考虑后面2~n位应该放入哪些数字。注意已经用过的数字不能再使用，需要使用一个数组st进行判重。

• 如下图，是n=4, k=10对应的情况：

代码

• C++

class Solution {
public:
    string getPermutation(int n, int k) {

        string res;
        for (int i = 1; i <= n; i++) res += to_string(i);
        for (int i = 0; i < k - 1; i++) {
            next_permutation(res.begin(), res.end());
        }
        return res;
    }
};

class Solution {
public:
    string getPermutation(int n, int k) {

        vector<int> fact(10, 1);  // 阶乘
        for (int i = 2; i < 10; i++) fact[i] = fact[i - 1] * i;

        string res;
        vector<bool> st(10);  // 判重数组
        for (int i = 0; i < n; i++)  // 枚举每个位置, 即res[i]应该填入哪个数字
            for (int j = 1; j <= n; j++)  // 枚举所有数字
                if (!st[j]) {  // j还没被使用过
                    if (fact[n - 1 - i] < k)   // 说明res[i]不应该放入j
                        k -= fact[n - 1 - i];
                    else {
                        res += to_string(j);
                        st[j] = true;
                        break;  // 表示res[i]已经填入了正确的数字
                    }
                }
        return res;
    }
};

• Java

class Solution {
    public String getPermutation(int n, int k) {

        int[] fact = new int[n];
        fact[0] = 1;
        for (int i = 1; i < n; i++) fact[i] = fact[i - 1] * i;

        StringBuilder sb = new StringBuilder();
        boolean[] st = new boolean[10];
        for (int i = 0; i < n; i++)
            for (int j = 1; j <= n; j++)
                if (!st[j]) {
                    if (fact[n - 1 - i] < k) k -= fact[n - 1 - i];
                    else {
                        sb.append((char)('0' + j));
                        st[j] = true;
                        break;
                    }
                }
        return sb.toString();
    }
}

时空复杂度分析

• 时间复杂度：$O(n^2)$。计数法中有两重循环。

• 空间复杂度：$O(n)$。