力扣(LeetCode)60. 排列序列(C++)

枚举

枚举每一位可能的数字。

如图。算法流程如上图。

思路分析 :
一个数 $n$ ，可以组成的排列数量有 $n!$ 。当首位确定，剩余位能组成的排列数量 $(n-1)!$ ，依次类推 $(n-2)!/(n-3)!/(n-4)!/\dots /2!/1!/0!$ 。对照算法流程图，发现，对于同一个位置，按字典序枚举，当权重 $k$ 大于当前位置确定后的排列数量时，我们减去这个排列数量；当权重 $k$ 小于等于排列当前位置确定后的排列数量时，就可以确定当前位置的数。

class Solution {
public:
    string getPermutation(int n, int k) {
        string ans;
        vector<bool> st(10,false);
        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(!st[j]){
                    if(fact<k) k-=fact;//枚举每一位数
                    else{
                        ans+=to_string(j);
                        st[j] = true;
                        break;
                    }
                }
            }
        }
        return ans ; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度 $O(n^2)$ ， 遍历 $n$ 个位置，对于每个位置枚举 $n$ 个数的时间复杂度 $O(n^2)$ 。

空间复杂度 $O(n)$ ，$bool$ 数组的空间复杂度 $O(n)$ 。

致语

理解思路很重要！
欢迎读者在评论区留言，答主看到就会回复的。

AC