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<Integer> 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<a.length;i++)
      {
          a[i] = i+1;
      }

      for(int i=1;i<k;i++)
      {
          a = getNextPermutation(a);
      }

      String string = "";
      for(int i=0;i<a.length;i++)
      {
          string+=a[i];
      }

      return string;
  }

  public int[] getNextPermutation(int []a)
  {

         int end = a.length-1;

         for(int i=end;i>=1;i--)
         {
             //寻找最早逆序的数
             if(a[i-1]<a[i])
             {

                 int k = i;
                 while(k<a.length && a[k]>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;

  }