Leetcode--Permutation Sequence

Leetcode--Permutation Sequence

Problem Description：

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):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

   Given n and k, return the kth permutation sequence.

   Note: Given n will be between 1 and 9 inclusive.

   分析：

   首先想到的暴力法，逐個的求排列，直到找到第k個排列，提交之後會超時，在網上搜索之後發現可以直接構造出第k個排列，以n = 4，k = 17為例，數組src = [1,2,3,...,n]。

   第17個排列的第一個數是什麼呢：我們知道以某個數固定開頭的排列個數 = (n-1)! = 3! = 6, 即以1和2開頭的排列總共6*2 = 12個，12 < 17, 因此第17個排列的第一個數不可能是1或者2，6*3 > 17, 因此第17個排列的第一個數是3。即第17個排列的第一個數是原數組（原數組遞增有序）的第m = upper(17/6) = 3（upper表示向上取整）個數。

   第一個數固定後，我們從src數組中刪除該數，那麼就相當於在當前src的基礎上求第k - (m-1)*(n-1)! = 17 - 2*6 = 5個排列，因此可以遞歸的求解該問題。

   代碼實現中注意一個小細節，就是一開始把k--，目的是讓下標從0開始，這樣下標就是從0到n-1，不用考慮n時去取余，更好地跟數組下標匹配。具體代碼如下：

   class Solution {
   public:
   
   	int fun(int n)
   	{
   		if(n<0)
   			return 0;
   		else if(n==0)
   			return 1;
   		else
   			return n*fun(n-1);
   	}
   
   	string getPermutation(int n, int k) {
   		string s;
   		int total=fun(n);
   		if(total flag(n,0);
   		//因為數組是從0到n-1的,所以基數從0到k-1  
   		--k;
   		for(int i=0;i