首页 > 代码库 > LeetCode: Permutation Sequcence 题解
LeetCode: Permutation Sequcence 题解
The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
"123""132""213""231""312""321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
--------------------------------------------------------------------------------------------------------------
题解： 套用DFS模版居然超时了。。。。看来lzDFS还是不过关啊！
lz怒了有木有，难道一定要DFS一个一个找吗？能不能直接找规律呢？
经过推算，lz终于找到一个规律了，0(N)就能搞定啊！！！
从全排列的产生可以看出，变化都是先从低位开始换位的。（此处高位指的是数组中下标减小的方向）
如果想引起A[i]的变化，需要A[i+1]~A[n]完成一次全排列，即需要 (n-i-1)! 次 这个结果即为 fac(n-i-1).
好吧，貌似好抽象！ 给一个形象地例子，尝试着解释一下：
1到9的阶乘如下
fac[1~9] 分别为： 1 2 6 24 120 720 5040 40320 362880-----------------------------------------------------------------------------输入 n=9 k=171996 src=http://www.mamicode.com/"123456789"如果 k=1 直接返回 src， 当输入为k时，实际需要变化的次数为 k-1次。因此 k=k-1 k=171995-----------------------------------------------------------------------------判断第1位是否需要更换： k> fac[8] : 171995>40320. 更换的下标为： 171996/40320 = 4 因此des[0]=src[4]=‘5’ des="5" 取出src[4] src=http://www.mamicode.com/"12346789" k%=fac[8] : k=10716判断第2位是否需要更换： k> fac[7] : 10715>5040. 更换的下标为： 10716/5040 = 2 因此des[2]=src[2]=‘3’。 des="53" 取出src[2] src=http://www.mamicode.com/"1246789" k%=fac[7] : k=635判断第3位是否需要更换： k< fac[6] : 635<720. src的首位不需要变化 因此des[3]=src[0]=‘1’。 des="531" 取出src[0] src=http://www.mamicode.com/"246789" k没有变化 k=635判断第4位是否需要更换： k> fac[5] : 635>120. 更换的下标为： 635/120 = 5 因此des[4]=src[5]=‘9’。 des="5319" 取出src[5] src=http://www.mamicode.com/"24678" k%=fac[5] k=35判断第5位是否需要更换： k> fac[4] : 35>24. 更换的下标为： 35/24 = 1 因此des[5]=src[1]=‘4’。 des="53194" 取出src[1] src=http://www.mamicode.com/"2678" k%=fac[4] k=11判断第6位是否需要更换： k> fac[3] : 11>6. 更换的下标为： 12/6 = 1 因此des[6]=src[1]=‘6’。 des="531946" 取出src[1] src=http://www.mamicode.com/"278" k%=fac[3] k= 5判断第7位是否需要更换： k> fac[2] : 5>2. 更换的下标为： 5/2 = 2 因此des[7]=src[2]=‘8’。 des="5319468" 取出src[1] src=http://www.mamicode.com/"27" k%=fac[2] k= 1判断第8位是否需要更换： k>= fac[1] : 1>=1. 更换的下标为： 1/1 = 1 因此des[7]=src[2]=‘7’。 des="53194687" 取出src[1] src=http://www.mamicode.com/"2" k%=fac[2] k= 0最后仅剩余src仅有1位，直接添加到des最后 des=”531946872“
ok，上代码！
1 class Solution { 2 public: 3 vector<int> fac; 4 string getPermutation(int n, int k) { 5 string src,des; 6 7 fac.resize(10,1); 8 for(int i=2;i<=n;i++) fac[i] = fac[i-1]*i; 9 10 if(k>fac[n]) return des;11 for(int m=1;m<=n;m++) src+=(‘0‘+m); //源字符串初始化12 13 k--;14 for(int j=n;j>1;j--)15 {16 if(k>=fac[j-1])17 {18 int temp = k/fac[j-1];19 k%=fac[j-1];20 des+=src[temp];21 src.erase(temp,1);22 }23 else24 {25 des+=src[0];26 src.erase(0,1);27 }28 }29 des+=src[0];30 return des;31 }32 };
转载请注明出处： http://www.cnblogs.com/double-win/ 谢谢！
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。