Kimi LeetCode 3470. 全排列 IV Java实现

LeetCode 3470. 全排列 IV — Java 实现解题思路这道题的核心是组合计数 逐位构造类康托展开不能暴力枚举全排列n 最大为 100。1. 交替排列相邻两数奇偶性必须不同。2. DP 计数dp[odd][even][lastParity] 表示剩余 odd 个奇数、even 个偶数且上一个数字的奇偶性为 lastParity0偶, 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但 n100 时交替排列数远超 long 范围。DP 值只需与 k 比较因此将所有值上限截断为 k1既防溢出又不影响正确性。4. 字典序构造从小到大枚举每个位置可选的数字利用 DP 值判断第 k 个排列落在哪个分支逐步确定每一位。---完整代码javaclass 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 个偶数上一个数字奇偶性为 p0偶, 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 变量”属于文本干扰/翻译错误标准解法无需此变量。