LeetCode -- Permutation Sequence

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;
    }
}