试填法+动态计数

lc3470

试填法+动态计数

class Solution {
public:
vector<int> permute(int n, long long k) {
using ll = long long;
auto get = [&](int x,int y)->ll{
//x个奇数，y个偶数，组内全排列，即阶乘，再乘到一起即为方案数
ll res = 1;
for(int i = 1;i <= max(x,y);i++){
if(i <= x){
res = res * i;
if(res > k) return k + 1;
}
if(i <= y){
res = res * i;
if(res > k) return k + 1;
}
}
return res;
};
//统计奇数偶数的数量
int o = n / 2 + (n % 2);
int e = n / 2;
vector<int> ans;
vector<bool> vis(n + 1,false);
for(int i = 0;i < n;i++){
for(int j = 1;j <= n;j++){
if(vis[j] || ans.size() && (ans.back() % 2 == j % 2)) continue;
if(n % 2 && i == 0 && j % 2 == 0) continue; //奇数长度时，第一个数必须填奇数
j % 2 ? o-- : e--;
ll cnt = get(o,e);
if(cnt < k){ //没有超过k个，跳过这cnt个
j % 2 ? o++ : e++;
k -= cnt;
}else{ //否则可填，最终k为1，表示当前情况下字典序最小的排列
vis[j] = true;
ans.push_back(j);
break;
}
}
}
if(ans.size() < n || k > 1) return {};
return ans;
}
};