题目链接：60. 第k个排列

题解：

依次考虑每一位，很是巧妙的做法！

题目简述：

求一个序列字典序的第k个排列！

题解一：

直接使用全排列函数：next_permutation()

第k个序列，就是要循环k - 1次。

时间复杂度：$O(n! \times k)$

AC代码一：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        for(int i = 1; i <= n; i++) res += i + '0';
        for(int i = 0; i < k - 1; i++){
            next_permutation(res.begin(), res.end());
        }
        return res;
    }
};

题解二：

计数

思路：

  • 从高到低依次考虑每一位
  • 对于每一位，从小到大枚举没有使用过的数，确定当前位

看下方的一个例子： n = 4, k = 10

第一位放1，后面有3！= 6种情况，放2后面也有3！= 6种情况，而k = 10，所以第一位一定是2，k = 10 - 6= 4

第二位放1，后面有2！= 2种情况，放3后面也有2！= 2种情况，而k = 4，所以第二位一定是3， k = 4 - 2 = 2

第三位放1，后面有1！= 1种情况，放4后面也有1！= 1种情况，而k = 2，所以第三位一定是4，k = 2 - 1 = 1

第四位放1，后面有1种情况，而k = 1, 所以第四位一定是1，k = 1

时间复杂度：$O(n^2)$

注意：

  • else内进入后即已经找到当前为改填的数，标记为true后直接break！

AC代码二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string getPermutation(int n, int k) {
        string res;
        vector<bool> vis(10);
        for(int i = 0; i < n; i++){
            int fact = 1;
            for(int j = 1; j <= n - i - 1; j++) fact *= j;
            for(int j = 1; j <= n; j++){
                if(!vis[j]){
                    if(fact < k) k -= fact;
                    else {
                        res += j + '0';
                        vis[j] = true;
                        break;
                    }
                }
            }
        }
        return res;
    }
};