当前位置：首页 > news >正文

LeetCode -- Permutation Sequence

news 来源：原创 2024/5/17 16:54:49

题目描述：

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"

参考了以下两篇文章的实现：
http://fisherlei.blogspot.sg/2013/04/leetcode-permutation-sequence-solution.html
http://www.programcreek.com/2013/02/leetcode-permutation-sequence-java/

实现代码：

public class Solution {
    public string GetPermutation(int n, int k) 
    {
        var nums = new List<int>();
    	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;
    }
}