题目

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 for n = 3:

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

Given n and k, return the _k_th permutation sequence.

Note:

  • Given n will be between 1 and 9 inclusive.
  • Given k will be between 1 and n! inclusive.

Example 1:

  1. Input: n = 3, k = 3
  2. Output: "213"

Example 2:

  1. Input: n = 3, k = 3
  2. Output: "213"

题意

按字典序输出一个递增序列的第k个排列。

思路

对于n个数的排列，只有当后面n-1个数完成一次全排列后，才会对第一个数进行更替，即更换周期cycle为(n-1)!，且第一个数字是按照n个数中从最小数到最大数依次更替的。令 0060. Permutation Sequence (M) - 图1，则排在第一位的数字是这n个数中的第count大，将该数字加入结果序列。每次得到第一位数字后，缩小n的规模求剩下n-1个数中应当排在第一位的数，同时要更新n-1个数中要求的第k个排列 0060. Permutation Sequence (M) - 图2。

笨办法：也可以结合0031. Next Permutation (M)，从递增序列开始依次计算下一个排列。

代码实现

Java

公式计算

  1. class Solution {
  2.     public String getPermutation(int n, int k) {
  3.         StringBuilder ans = new StringBuilder();
  4.         boolean[] used = new boolean[n];        //标记剩下的数字
  6.         while (n >= 1) {
  7.             // 注意n=1时实际周期为0，将其周期设为1便于合并处理
  8.             int cycle = n == 1 ? 1 : factorial(n - 1);
  9.             int count = (k - 1) / cycle + 1;
  11.             // 找到剩余数字中的第count大，并将其加入结果序列
  12.             for (int i = 0; i < used.length; i++) {
  13.                 if (!used[i]) {
  14.                     if (count == 1) {
  15.                         ans.append(i + 1);
  16.                         used[i] = true;
  17.                         break;
  18.                     }
  19.                     count--;
  20.                 }
  21.             }
  23.             // 缩小待排列序列的规模
  24.             n--;
  25.             k = (k - 1) % cycle + 1;
  26.         }
  28.         return ans.toString();
  29.     }
  31.     private int factorial(int n) {
  32.         int ans = 1;
  33.         while (n != 1) {
  34.             ans *= n--;
  35.         }
  36.         return ans;
  37.     }
  38. }

nextPermutation

  1. class Solution {
  2.     public String getPermutation(int n, int k) {
  3.         char[] a = new char[n];
  4.         for (int i = 0; i < n; i++) {
  5.             a[i] = (char) (i + 1 + '0');
  6.         }
  7.         int count = 1;
  8.         while (count < k) {
  9.             nextPermutation(a);
  10.             count++;
  11.         }
  12.         return String.valueOf(a);
  13.     }
  15.     // 依照当前排列计算下一个排列
  16.     private void nextPermutation(char[] a) {
  17.         int i = a.length - 2;
  18.         while (i >= 0 && a[i] >= a[i + 1]) {
  19.             i--;
  20.         }
  21.         // i==-1说明整个数组是逆序排列，已经是字典序中的最后一个排列
  22.         if (i == -1) {
  23.             return;
  24.         }
  25.         int j = a.length - 1;
  26.         while (a[j] <= a[i]) {
  27.             j--;
  28.         }
  29.         swap(a, i, j);
  30.         reverse(a, i + 1, a.length - 1);
  31.     }
  33.     private void reverse(char[] a, int left, int right) {
  34.         while (left < right) {
  35.             swap(a, left++, right--);
  36.         }
  37.     }
  39.     private void swap(char[] a, int i, int j) {
  40.         char temp = a[i];
  41.         a[i] = a[j];
  42.         a[j] = temp;
  43.     }
  44. }

JavaScript

公式计算

  1. /**
  2.  * @param {number} n
  3.  * @param {number} k
  4.  * @return {string}
  5.  */
  6. var getPermutation = function (n, k) {
  7.   let used = new Array(n)
  8.   let ans = ''
  10.   while (n > 0) {
  11.     let cycle = n === 1 ? 1 : factorial(n - 1)
  12.     let rank = Math.trunc((k - 1) / cycle) + 1
  13.     let count = 0
  14.     for (let i = 0; i < used.length; i++) {
  15.       if (!used[i]) {
  16.         count++
  17.         if (count === rank) {
  18.           ans += i + 1
  19.           used[i] = true
  20.           break
  21.         }
  22.       }
  23.     }
  24.     k = ((k - 1) % cycle) + 1
  25.     n--
  26.   }
  28.   return ans
  29. }
  31. let factorial = function (n) {
  32.   return n === 1 ? n : n * factorial(n - 1)
  33. }

nextPermutation

  1. /**
  2.  * @param {number} n
  3.  * @param {number} k
  4.  * @return {string}
  5.  */
  6. var getPermutation = function (n, k) {
  7.   let count = 1
  8.   let arr = new Array(n).fill(0).map((v, index) => index + 1)
  9.   while (count !== k) {
  10.     nextPermutation(arr)
  11.     count++
  12.   }
  13.   return arr.join('')
  14. }
  16. let nextPermutation = function (arr) {
  17.   let i = arr.length - 2
  18.   while (i >= 0 && arr[i] >= arr[i + 1]) {
  19.     i--
  20.   }
  21.   if (i === -1) {
  22.     return
  23.   }
  24.   let j = arr.length - 1
  25.   while (arr[i] >= arr[j]) {
  26.     j--
  27.   }
  28.   [arr[i], arr[j]] = [arr[j], arr[i]]
  29.   let left = i + 1,
  30.     right = arr.length - 1
  31.   while (left < right) {
  32.     [arr[left++], arr[right--]] = [arr[right], arr[left]]
  33.   }
  34. }