首页 > 代码库 > Leetcode#60 Permutation Sequence
Leetcode#60 Permutation Sequence
原题地址
一个一个模拟肯定要超时，只有生算找规律呗。
比如n=4，k=10，先将n=4的所有排列写出来：
(1) 1 2 3 4(2) 1 2 4 3(3) 1 3 2 4(4) 1 3 4 2(5) 1 4 2 3(6) 1 4 3 2(7) 2 1 3 4(8) 2 1 4 3(9) 2 3 1 4(10) 2 3 4 1 <-- 目标序列(11) 2 4 1 3(12) 2 4 3 1(13) 3 1 2 4(14) 3 1 4 2(15) 3 2 1 4... (省略后面的)假设最终的结果是ABCD
首先确定A。因为k=10 > 3!=6，所以可以算出A应该是1~n里面的第 ceiling{k / 3!}=2个（ceiling表示取上整），即A=2。最后把2从1~n中删除，更新k，令k=k%3!=4
然后确定B。因为k=4 > 2!=2，所以可以算出B应该是1~n里面的第ceiling{k/2!}=2个，因为2之前被删掉了，所以现在第2个数字是3，即B=3。最后把3从1~n中删除，更新k=k%2!=2
接着看C。因为k=0，说明我们要求的序列肯定是某个序列的结尾处，所以之后的数字依次按照从大到小的方式输出即可，即C=4。把4从1~n中删除，继续。
最后看D。因为k=0，同上，可得D=1。
（写的有些抽象，以后有时间再加工吧...）
代码：
1 string getPermutation(int n, int k) { 2 string res(n, 0); 3 vector<char> avail(n, 0); 4 int p = 1; 5 for (int i = 1; i <= n; i++) { 6 p *= i; 7 avail[i - 1] = i + ‘0‘; 8 } 9 10 for (int i = 0; i < n; i++) {11 if (k > 0) {12 int nextp = p / (n - i);13 int order = (k - 1) / nextp;14 res[i] = avail[order];15 avail.erase(avail.begin() + order);16 k %= nextp;17 p = nextp;18 }19 else {20 res[i] = avail.back();21 avail.pop_back();22 }23 }24 25 return res;26 }
Leetcode#60 Permutation Sequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。