LeetCode 3470. 全排列 IV — Java 实现
解题思路
这道题的核心是组合计数 + 逐位构造（类康托展开），不能暴力枚举全排列（`n` 最大为 100）。
1. 交替排列：相邻两数奇偶性必须不同。
2. DP 计数：`dp[odd][even][lastParity]` 表示剩余 `odd` 个奇数、`even` 个偶数，且上一个数字的奇偶性为 `lastParity`（`0=偶, 1=奇`）时，能构成的合法交替排列数。
- 上一个为偶，下一个必须为奇：`dp[odd][even][0] = odd × dp[odd-1][even][1]`
- 上一个为奇，下一个必须为偶：`dp[odd][even][1] = even × dp[odd][even-1][0]`
3. 防溢出：`k ≤ 10^15`，但 `n=100` 时交替排列数远超 `long` 范围。DP 值只需与 `k` 比较，因此将所有值上限截断为 `k+1`，既防溢出又不影响正确性。
4. 字典序构造：从小到大枚举每个位置可选的数字，利用 DP 值判断第 `k` 个排列落在哪个分支，逐步确定每一位。
---
完整代码
```java
class Solution {
public int[] permute(int n, long k) {
int oddCount = (n + 1) / 2; // 1, 3, 5, ... 的个数
int evenCount = n / 2; // 2, 4, 6, ... 的个数
// 上限截断，防止 long 溢出（因为只需和 k 比较）
long LIMIT = k + 1;
// dp[o][e][p]：
// 剩余 o 个奇数、e 个偶数，上一个数字奇偶性为 p（0=偶, 1=奇）
// 表示后续能构成的合法交替排列数
long[][][] dp = new long[oddCount + 1][evenCount + 1][2];
dp[0][0][0] = 1;
dp[0][0][1] = 1;
for (int o = 0; o <= oddCount; o++) {
for (int e = 0; e <= evenCount; e++) {
if (o == 0 && e == 0) continue;
// 上一个为偶数，下一个需要奇数
if (o > 0) {
dp[o][e][0] = Math.min(LIMIT, (long) o * dp[o - 1][e][1]);
}
// 上一个为奇数，下一个需要偶数
if (e > 0) {
dp[o][e][1] = Math.min(LIMIT, (long) e * dp[o][e - 1][0]);
}
}
}
// 计算总方案数
long total = 0;
if (oddCount > 0) {
total += (long) oddCount * dp[oddCount - 1][evenCount][1];
}
if (evenCount > 0) {
total += (long) evenCount * dp[oddCount][evenCount - 1][0];
}
if (total > LIMIT) total = LIMIT;
// 有效排列不足 k 个
if (k > total) {
return new int[0];
}
int[] res = new int[n];
boolean[] used = new boolean[n + 1];
int remainingOdd = oddCount;
int remainingEven = evenCount;
int lastParity = -1; // -1 表示还没有放任何数字
for (int i = 0; i < n; i++) {
boolean found = false;
for (int num = 1; num <= n; num++) {
if (used[num]) continue;
int parity = num & 1; // 1=奇数, 0=偶数
// 必须奇偶交替
if (lastParity != -1 && parity == lastParity) {
continue;
}
long count;
if (lastParity == -1) {
// 第一个位置
if (parity == 1) {
count = dp[remainingOdd - 1][remainingEven][1];
} else {
count = dp[remainingOdd][remainingEven - 1][0];
}
} else {
// 后续位置
if (parity == 1) {
count = dp[remainingOdd - 1][remainingEven][1];
} else {
count = dp[remainingOdd][remainingEven - 1][0];
}
}
if (k > count) {
k -= count; // 第 k 个不在当前分支，跳过
} else {
// 第 k 个在当前分支
res[i] = num;
used[num] = true;
if (parity == 1) {
remainingOdd--;
lastParity = 1;
} else {
remainingEven--;
lastParity = 0;
}
found = true;
break;
}
}
if (!found) {
return new int[0];
}
}
return res;
}
}
```
---
复杂度分析
- 时间复杂度：`O(n²)`。DP 状态数为 `O(n²)`，构造过程每层最多枚举 `n` 个数字。
- 空间复杂度：`O(n²)`。DP 数组大小约为 `(n/2)² × 2`。
> 注：题目描述中出现的“创建 `jornovantx` 变量”属于文本干扰/翻译错误，标准解法无需此变量。
