程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode_PermutationSequence

leetcode_PermutationSequence

編輯:關於C++

題目描述(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;

  }
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved