leetcode_PermutationSequence

leetcode_PermutationSequence

題目描述(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和k，求{1,2，3…n}的全排列中第k個排列。對於全排列我們可以通過遞歸去窮舉求解或者從“123…n”依次生成下一個序列，有一個很典型的getNextPermutation的算法，是給定排列求下一個排列，c++ STL中有實現，其基本思路是從尾部掃描找到第一個逆序點，然後將此點和尾部數值交換，然後對逆序點後面的序列進行逆序reverse，即可得到下一個排列，詳細過程可以去搜索一下，我下面也有此代碼，我最初是想通過計算k次(或是k-1)nextPermutation來求解，結果發現超時TLE，由於題目要求我們結算第K個，那麼我們把前面的也都計算出來，顯然做了很過無用功，實際上可以通過數學方法對N，K運算，依次得到我們第一位到第N位的數值。

詳細代碼

//算法思想就是根據K和n一次可以計算出第一個位置~第n個位置的數，應用數學方法，看到代碼可以很好理解。
  //題目要求從1計數，我們將k->k-1 從0計數，便於寫代碼。
  //以第一個位置的數為例，用k(k已經變為k-1)除以(n-1)! 得到index，List.get(index)就是第一個位置的數，然後從集合中刪除此數
  //k->k%(n-1)! 下一次在運算的時候除以(n-2)! k也對(n-2)!求余，然後得到index再從list中刪除此數，作為第二個位置的數
  //注意邊界情況，數組越界以及除數為0的情況
  public String getPermutation_math(int n, int k) 
  {
      k = k-1;//我們程序是從0計數
      List list = new LinkedList<>();
      StringBuilder resultBuilder = new StringBuilder();
      int cal = 1;
      for(int i=1;i<=n;i++)
      {
          list.add(i);
          cal = cal*i;
      }

      cal = cal/n; //n-1 階乘

      for(int i=1;i<=n;i++)
      {
          if(i==n)
          {
              //只有最後一個直接連接，不在進行運算，因為cal/(n-i)會出現0的情況
              resultBuilder.append(list.get(0));
              break;
          }

          int index = k/cal;

          resultBuilder.append(list.get(index));
          list.remove(index);


          k = k%cal;
          cal = cal/(n-i);

//        if(k==0)
//        {
//            //k==0不再進行計算 直接連接後面的 也可以不加這個，程序後續計算也相當於下面這段代碼
//            for(Integer integer:list)
//            {
//                resultBuilder.append(integer);
//            }
//            break;
//        }
      }
      return resultBuilder.toString();


  }

補充

(超時代碼以及getNextPermutation函數實現)

  //得到"123...n"的第k個全排列 
  public String getPermutation(int n, int k) 
  {
      int a[] = new int[n];
      for(int i=0;i=1;i--)
         {
             //尋找最早逆序的數
             if(a[i-1]a[i-1])
                 {
                     k++;
                 }
                 k = k-1; //對應的k值

                 //交換數值i-1 和 k k為右邊大於a[i-1]的最小值
                 int tmp = a[k];
                 a[k] = a[i-1];
                 a[i-1] = tmp;

                 //逆序 i->a.length-1
                 for(int j = a.length-1, t = i; j>t; j--,t++)
                 {
                     tmp = a[j];
                     a[j] = a[t];
                     a[t] = tmp;
                 }
                 return a;
             }
     }

     return a;

  }