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