Leetcode 60-第k个排列

题意

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

1. “123”
2. “132”
3. “213”
4. “231”
5. “312”
6. “321”

给定 n 和 k，返回第 k 个排列。

示例1:

输入: n = 3, k = 3
输出: "213"

示例2:

输入: n = 4, k = 9
输出: "2314"

思路

1. 全排列算法（笨笨）

   给定一个排列a，题中生成下一个排列b的方法实际上是寻找一个使得a增加值最小的排列，该排列即为排列b。

   其算法描述如下：

   1. 从右到左扫描当前排列，寻找第一个相邻递减数字。递减的数字称为Partition Number。
   2. 从右到左扫描当前排列，寻找第一个比Partition Number大的数字。称其为Change Number。
   3. 交换Partition Number和Change Number。
   4. 逆向Partition Number所在位置右边的所有数字。

   完成以上四步操作即可得到使得排列a增加值最少的排列b。

   根据题中的描述，只需要对排列 12...n 执行 k-1 次该算法即可得到答案。

   class Solution {
       public String nextPermutation(String v) {
           StringBuilder sb = new StringBuilder(v);
   
           // 从右到左扫描第一个相邻递减数字，即Partition Number
           int len = v.length(), pn = len;
           for (int i = len - 2; i >= 0; i--)
               if (v.charAt(i) < v.charAt(i + 1)){
                   pn = i;
                   break;
               }
   
           if (pn == len) // 到达最后一个排列返回自身
               return v.toString();
   
           // 从右到左寻找第一个比Partition Number大的数字，称之为Change Number
           int cn = len;
           for (int i = len - 1; i > pn; i--)
               if (v.charAt(i) > v.charAt(pn)) {
                   cn = i;
                   break;
               }
   
           // 交换PN和CN
           char tmp = sb.charAt(pn);
           sb.setCharAt(pn, sb.charAt(cn));
           sb.setCharAt(cn, tmp);
   
           // 逆向PN右侧的数，得到结果
           String s = sb.substring(pn + 1);
           sb.delete(pn + 1, len);
           
           StringBuilder sb2 = new StringBuilder(s);
           sb.append(sb2.reverse().toString());
           return sb.toString();
       }
   
       public String getPermutation(int n, int k) {
           StringBuilder sb = new StringBuilder();
           for (int i = 1; i <= n; i++)
               sb.append(i);
           
           String ans = sb.toString();
           for (int i = 1; i < k; i++)
               ans = nextPermutation(ans);
           return ans;
       }
   }