leetcode 60:第k个排列

本文主要是介绍leetcode 60:第k个排列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

直接使用全排列之后再进行提取，会超出时间限制。

本题限定了1-9可以使用简单的方式

比如 n=5;k=50;

数组为1,2,3,4,5

首先是(n-1)!=24  第一个元素应该为50/24+1 , 也就是3，代表的是没使用数组的第3个元素，也即为3,k=50%24=2

第二个元素（n-2)!=6 元素应该为2/6+1 ,也就是1 代表的是没使用的数组的第1个元素，也即1 ,k=2%6=2

第三个 元素（n-3)!=2   2/2=1 代表的是没使用的元素的第1个元素  应该数组中1已经使用  第一个没使用的即为2 ，

因为2%2==0，所以后面两个元素是降序的没使用的元素  也就是5 4

所以字符串为31254

int getN(int n){if(n<=1)return 1;elsereturn n*getN(n-1);
}std::string getPermutation(int n, int k) {std::vector<int> a;std::vector<int> b;for(int i=0;i<n;i++){a.push_back(i+1);b.push_back(0);}std::string str="";while(n!=0){int c=getN(n-1);if(k%c==0){k=k/c;int d=0;for(int i=0;i<a.size();i++){if(b[i]==0)d++;if(d==k){b[i]=1;d=i;break;}}char re[10];sprintf(re,"%d",a[d]);str+=re;for(int j=a.size()-1;j>=0;j--){if(b[j]!=1){sprintf(re,"%d",a[j]);str+=re;}}break;}else{int f=k/c+1;k=k%c;int d=0;for(int i=0;i<a.size();i++){if(b[i]==0)d++;if(d==f){b[i]=1;d=i;break;}}char re[10];sprintf(re,"%d",a[d]);str+=re;n--;}}return str;
}

 

这篇关于leetcode 60:第k个排列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---