class Solution {
public:
int num=0;
bool isgo=true;
public:
string getPermutation(int n, int k) {
vector<int> nums;
for(int i=1;i<=n;++i)
nums.push_back(i);
vector<vector<int>> res;
vector<int> path;
string str;
trackback(res,path,nums,k,str);
return str;
}
void trackback(vector<vector<int>> &res,vector<int> &path,vector<int> &nums,int k,string &str)
{
if(path.size() == nums.size())
{
res.push_back(path);
num++;
if(num == k)
{
for(auto c:path)
{
str+=char(c+48);
}
isgo=false;
}
return ;
}
if(!isgo)//强制递归停止，层层返回
return ;
for(auto i:nums)
{
auto pos=find(path.begin(),path.end(),i);
if(pos==path.end())
{
path.push_back(i);
trackback(res,path,nums,k,str);
path.pop_back();
}
}
}
};
但是这个方法超时
康托逆展开编辑
例1 {1,2,3,4,5}的
全排列，并且已经从小到大排序完毕
(1)找出第96个数
首先用96-1得到95
用95去除4! 得到3余23
有3个数比它小的数是4
所以第一位是4
用23去除3! 得到3余5
有3个数比它小的数是4但4已经在之前出现过了所以第二位是5（4在之前出现过，所以实际比5小的数是3个）
用5去除2!得到2余1
有2个数比它小的数是3，第三位是3
用1去除1!得到1余0
有1个数比它小的数是2，第二位是2
最后一个数只能是1
所以这个数是45321
class Solution {
public:
string getPermutation(int n, int k) {
int tbl[]= { 1,2,6,24,120,720,5040,40320,362880 };
if( k > tbl[n-1] ) return "";
vector<int> used { 1,2,3,4,5,6,7,8,9 };
string s(n, '0');
int i=n-1, j=0, o, u;
while( j < n ) {
o = ( i == 0 ? 0 : (k-1)/tbl[i-1]);
u = used[o];
s[j++] = u + '0';
used.erase(used.begin() + o);
k = k - o*tbl[(i--)-1];
}
return s;
}
};
看了这个高手的代码，真的是心情愉悦，还有更精简的吗？
转载于:https://www.cnblogs.com/yanqi110/p/4933074.html
相关资源：数据结构—成绩单生成器
