LeetCode 3470. 全排列 IV — TypeScript 实现解题思路与之前版本一致采用 组合计数 DP 逐位构造1. DP 状态dp[o][e][p] 表示剩余 o 个奇数、e 个偶数且上一个数字的奇偶性为 p0偶, 1奇时后续能构成的合法交替排列数。2. 防溢出k ≤ 10¹⁵ 在 JavaScript number 的安全整数范围内MAX_SAFE_INTEGER ≈ 9×10¹⁵但 DP 中间值可能溢出因此将 DP 值上限截断为 k 1。3. 字典序构造从小到大枚举每一位可选数字利用 DP 值判断第 k 个排列所在分支。---完整代码typescriptfunction permute(n: number, k: number): number[] {const oddCount Math.floor((n 1) / 2); // 1, 3, 5, ... 的个数const evenCount Math.floor(n / 2); // 2, 4, 6, ... 的个数const LIMIT k 1;// dp[o][e][p]// 剩余 o 个奇数、e 个偶数上一个数字奇偶性为 p0偶, 1奇const dp: number[][][] Array.from({ length: oddCount 1 }, () Array.from({ length: evenCount 1 }, () [0, 0]));dp[0][0][0] 1;dp[0][0][1] 1;for (let o 0; o oddCount; o) {for (let e 0; e evenCount; e) {if (o 0 e 0) continue;// 上一个为偶数下一个需要奇数if (o 0) {dp[o][e][0] Math.min(LIMIT, o * dp[o - 1][e][1]);}// 上一个为奇数下一个需要偶数if (e 0) {dp[o][e][1] Math.min(LIMIT, e * dp[o][e - 1][0]);}}}// 计算总方案数let total 0;if (oddCount 0) {total oddCount * dp[oddCount - 1][evenCount][1];}if (evenCount 0) {total evenCount * dp[oddCount][evenCount - 1][0];}total Math.min(LIMIT, total);// 有效排列不足 k 个if (k total) {return [];}const res: number[] [];const used new Array(n 1).fill(false);let remainingOdd oddCount;let remainingEven evenCount;let lastParity -1; // -1 表示还没有放任何数字let kk k;for (let i 0; i n; i) {let found false;for (let num 1; num n; num) {if (used[num]) continue;const parity num 1; // 1奇数, 0偶数// 必须奇偶交替if (lastParity ! -1 parity lastParity) {continue;}// 计算选择当前数字后剩余位置的方案数const count parity 1? dp[remainingOdd - 1][remainingEven][1]: dp[remainingOdd][remainingEven - 1][0];if (kk count) {kk - count; // 第 kk 个不在当前分支跳过} else {// 第 kk 个在当前分支res.push(num);used[num] true;if (parity 1) {remainingOdd--;lastParity 1;} else {remainingEven--;lastParity 0;}found true;break;}}if (!found) {return [];}}return res;}---复杂度分析- 时间复杂度O(n²)。DP 填充为 O(n²)构造过程每层最多枚举 n 个数字。- 空间复杂度O(n²)。DP 数组大小约为 (n/2)² × 2。 TypeScript/JavaScript 的 number 类型为 IEEE 754 双精度浮点数最大安全整数约为 9×10¹⁵足以覆盖本题 k ≤ 10¹⁵ 的范围。DP 值截断到 LIMIT k 1 后所有运算均在安全整数范围内进行无需使用 BigInt。