LeetCode -- Permutation Sequence

来源:转载

题目描述:


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.


对于n,先构造从1到n的数字序列s(例如3,s=123),对于s的所有全排列情况,求出第k种排列的字符串。
例如对于123,第3种排列的情况为213。


思路:
1.本题属于排列问题,一开始想到的是回溯。可发现题目只要求求出第k种情况,因此没必要track所有的排列状态导致浪费空间,并且这种算法会超时。
2.使用nums[0...n]存放数字1到n(例如123,nums为{1,2,3}),循环n次,每次从nums中拿走一个元素。试图找到k与(n-1)!的关系,求出每次要拿的索引,每次循环更新k值。


分析:
假设n=4,s为1234, 要找出第8种排列,
第1轮:先对后面3个元素进行全排列,可以得到3!种排列依然小于8(还差2种),而此时可以拿到第7(即k-1)/3!个元素:n[1]=2。而此时k更新为7%3! = 1;
第2轮:接下来的任务是,从134中找到第1/2!个元素,即n[0]=1。k更新为1%2!=1;
第3轮:在34中拿到第1/1!个元素,即n[1]=4。对k更新:k=1%1!=0;
第4轮:将最后1个元素n[3]拿出,即3。


最后的结果为2143
 
实现代码:

public class Solution { public string GetPermutation(int n, int k) { var nums = new List(); var total = 1; for(var i = 1;i <= n; i++) { total *= i; nums.Add(i); } var ret = ; k--; while(n > 0) { // total represent as (n-1)! total /= n; // take the nums[k / (n-1)!] element var index = k / total; var x = nums[index]; ret += x; nums.RemoveAt(index); // next k would be k%(n-1)! k = k % total; n--; } return ret; }}


 



分享给朋友:
您可能感兴趣的文章:
随机阅读: