盒子
盒子

59_第k个排列_leetcode

给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:
“123”
“132”
“213”
“231”
“312”
“321”
给定 n 和 k,返回第 k 个排列。
说明:
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。

输入: n = 3, k = 3
输出: “213”
输入: n = 4, k = 9
输出: “2314”

题解: 逆康托展开 康托展开是一个全排列到一个自然数的双射,常用于构建hash表时的空间压缩。设有n个数(1,2,3,4,…,n),可以有组成不同(n!种)的排列组合,
康托展开表示的就是是当前排列组合在n个不同元素的全排列中的名次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public String getPermutation(int n, int k) {
int[] digit = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
List<Integer> digitList = Arrays.stream(digit).boxed().collect(Collectors.toList());
int[] factor = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
StringBuilder sb = new StringBuilder();
k--;
while (n > 0) {
int val = k / factor[n - 1];
sb.append(digitList.get(val + 1));
digitList.remove(val + 1);
k = k % factor[n - 1];
n--;
}
return sb.toString();
}
}

AC传送门leetcode

支持一下
扫一扫,支持沈健
  • 微信扫一扫
  • 支付宝扫一扫