[LeetCode][Java] Permutation Sequence

[LeetCode][Java] 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):

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.

   題意：

   集合[1,2,3,…,n] 包含一共n!不同的存在且唯一的組合。

   通過按順序列出並標記這些所有的組合。我們得到下面這個序列（當n = 3 的時候）：

    

   1. 123
   2. 132
   3. 213
   4. 231
   5. 312
   6. 321 給定 n 和 k,返回序列中的第 k 個元素。n 為 1 到 9 之間的一個數。

       

      算法分析：

      方法一：

      利用了題目《permutations》的方法，先得到所有的排列，然後找出第 k 個元素，但是超時了，後面也給出代碼吧

      方法二：

      參考博客http://www.cnblogs.com/springfor/p/3896201.html

       

      數學的解法，適用度不高，僅限於這題，了解一下吧。

       

      題目告訴我們：對於n個數可以有n!種排列；那麼n-1個數就有(n-1)!種排列。

      那麼對於n位數來說，如果除去最高位不看，後面的n-1位就有 (n-1)!種排列。

      所以，還是對於n位數來說，每一個不同的最高位數，後面可以拼接(n-1)!種排列。

      所以你就可以看成是按照每組(n-1)!個這樣分組。

      利用 k/(n-1)! 可以取得最高位在數列中的index。這樣第k個排列的最高位就能從數列中的index位取得，此時還要把這個數從數列中刪除。

      然後，新的k就可以有k%(n-1)!獲得。（恕我愚笨，現在也沒想明白為啥要這麼更新k~~）

      循環n次即可。 同時，為了可以跟數組坐標對其，令k先--。

      
      

      AC代碼：

      方法一：（超時了）

       

         public String getPermutation(int n, int k) 
          {
      		int num[]=new int[n];
      		ArrayList> temres= new ArrayList>();
      		for(int i=0;i> permute(int[] num) 
          {
          	ArrayList> result = new ArrayList>();
          	permute(num, 0, result);
          	return result;
          }
          static void permute(int[] num, int start, ArrayList> result) 
          {
          	if (start >= num.length) //終止條件，遞歸到末尾節點是，將數組轉化為鏈表
          	{
          		ArrayList item = convertArrayToList(num);
          		result.add(item);
          	}
          	for (int j = start; j <= num.length - 1; j++)
          	{
          		swap(num, start, j);//交換
          		permute(num, start + 1, result);//交換後子代遞歸
          		swap(num, start, j);//恢復到交換前的初始狀態，以便於得出下一次的交換結果
          	}
          }
          private static ArrayList convertArrayToList(int[] num) //數組變鏈表
          {
          	ArrayList item = new ArrayList();
          	for (int h = 0; h < num.length; h++) 
          		item.add(num[h]);
          	return item;
          }
          private static void swap(int[] a, int i, int j) //交換
          {
          	int temp = a[i];
          	a[i] = a[j];
          	a[j] = temp;
          }

      
      方法二：

       

       

          public String getPermutation(int n, int k) 
          {  
              k--;//to transfer it as begin from 0 rather than 1
              
              List numList = new ArrayList();  
              for(int i = 1; i<= n; i++)
                  numList.add(i);
             
              int factorial = 1;    
              for(int i = 2; i < n; i++)  
                  factorial *= i;    
              
              StringBuilder res = new StringBuilder();//StringBuffer的簡易替換|用在字符串緩沖區被單個線程使用時|它比StringBuffer要快(most of time)
              int times = n-1;
              while(times>=0)
              {
                  int indexInList = k/factorial;
                  res.append(numList.get(indexInList));  
                  numList.remove(indexInList);  
                  
                  k = k%factorial;//new k for next turn
                  if(times!=0)
                      factorial = factorial/times;//new (n-1)!
                  
                  times--;
              }
              
              return res.toString();
          }