枚举

枚举每一位可能的数字。

如图。算法流程如上图。

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

class Solution {
public:string getPermutation(int n, int k) {string ans;vector st(10,false);for(int i = 0 ;iint fact = 1;for(int j = 1;j<=n-i-1;j++) fact*=j;for(int j = 1;j<=n;j++){if(!st[j]){if(factans+=to_string(j);st[j] = true;break;}}}}return ans ; }
};

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

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

致语

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

AC