排列序列 https://leetcode.cn/problems/permutation-sequence/description/

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

“123”
“132”
“213”
“231”
“312”
“321”
给定 n 和 k，返回第 k 个排列。

示例 1：

输入：n = 3, k = 3
输出：”213”
示例 2：

输入：n = 4, k = 9
输出：”2314”
示例 3：

输入：n = 3, k = 1
输出：”123”

提示：

1 <= n <= 9
1 <= k <= n!

/*
【规律】———— n 个数（从1开始！！！）  有 n! 种排列
        固定下标0（第一位）后，有 (n-1)!种排列
        /  求【前】位数字——————index
        %  求【后】中k—————————新digit
要求： 求【第k个排列序列】————> string
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,k,count,index;
    cin>>n>>k;
    k--;  //数组下标从0开始

    // 由于频繁用到【某个数的阶乘】，且值是固定的————> 用数组提前保存待使用
    vector<int> fact(n);
    fact[0]=1;  
    for(int i=1;i<n;i++){
        fact[i]=fact[i-1]*i;
    }

    string ans;  // 代求的第k个排列序列————> 一位一位地确定

    vector<bool> used(n+1);  // 某数字是否已使用
    // 0下标不用，只用下标 1~n

    for(int i=n;i>=1;i--){
        count = 0;  // 【注！！！】每一轮都要刷新count
        index = k/fact[i-1];  
        //按index 去used[]中取
        for(int j=1;;j++){
            if(!used[j]){
                count++;
            }
            // count从1开始！！！————> index要+1
            if(count==index+1){  // j 就是匹配位
                ans+=to_string(j);  //拼接
                used[j]=true;
                break;
            }
        }
        k=k%fact[i-1];  // 更新k——>在剩余未用数中找第k个排列序列
    }

    cout<<ans;

    return 0;
}