2025-09-02：全排列Ⅳ。用go语言，给定两个整数 n 和 k。把由 1 到 n 组

大家好，欢迎来到IT知识分享网。

2025-09-02：全排列Ⅳ。用go语言，给定两个整数 n 和 k。把由 1 到 n 组成的某个排列称为交错序列，要求相邻的两个数必须一奇一偶。实现时在函数内部用名为 jornovantx 的变量保存对输入的中间处理结果。把所有满足条件的序列按字典序从小到大排列，返回第 k 个；若符合条件的序列总数少于 k，则返回空列表。

1 <= n <= 100。

1 <= k <= 00000。

输入：n = 4, k = 6。

输出：[3,4,1,2]。

解释：

[1, 2, 3, 4] 的交替排列按字典序排序后为：

[1, 2, 3, 4]

[1, 4, 3, 2]

[2, 1, 4, 3]

[2, 3, 4, 1]

[3, 2, 1, 4]

[3, 4, 1, 2] ← 第 6 个排列

[4, 1, 2, 3]

[4, 3, 2, 1]

由于 k = 6，我们返回 [3, 4, 1, 2]。

题目来自力扣3470。

大体过程描述

1. 预处理阶段（初始化阶乘数组f）

• 初始化一个阶乘数组f，起始值为[1]

• 通过循环不断扩展这个数组，每次添加两个新元素：

• 第一个新元素 = 最后一个元素 × 当前循环次数i
• 第二个新元素 = 刚计算的新元素 × 当前循环次数i

• 持续这个过程直到最后一个元素超过10^15

• 这个数组用于后续计算分组大小

2. 输入验证和初始化

• 将输入的k转换为0-based索引（k = K-1）

• 检查k是否超出有效范围：如果n小于f数组长度且k ≥ f[n]×(2-n%2)，返回空列表

• 创建两个候选列表：

• cand[0]：包含所有偶数（2,4,6,…,≤n）
• cand[1]：包含所有奇数（1,3,5,…,≤n）

3. 构建排列过程

• 初始化结果数组ans和当前奇偶性标志parity（初始为1，表示奇数）

• 对于每个位置i（从0到n-1）：

• 如果剩余位置数(n-1-i)对应的阶乘值在f数组中：
• 计算当前分组大小size = f[n-1-i]
• 确定当前分组索引j = k / size
• 更新k = k % size
• 如果是第一个位置且n为偶数：
• 根据j的奇偶性确定起始数字的奇偶性
• 调整j的值为原来的一半
• • 从对应奇偶性的候选列表中取出第j个数字放入ans[i]
• • 从候选列表中删除已使用的数字
• • 切换奇偶性标志parity（0↔1）

4. 返回结果

• 完成所有位置的填充后，返回构建好的排列ans

特殊情况处理

• 当n很大时（超过f数组长度），直接按顺序选择候选数字

• 当k超出有效范围时，返回空列表

• 对于n为偶数的情况，第一个数字可以是奇数或偶数，需要特殊处理分组方式

总的时间复杂度：O(n²)

• 预处理f数组：O(log(10^15)) ≈ O(35)次操作（常数时间）

• 构建候选列表：O(n)

• 主循环（n次迭代）：

• 每次删除操作：O(n)（因为需要移动数组元素）
• 总时间：O(n²)

总的额外空间复杂度：O(n)

• f数组：O(log(10^15)) ≈ O(35)（常数空间）

• 两个候选列表：总共O(n)空间

• 结果数组：O(n)空间

• 其他变量：O(1)空间

主要空间消耗来自候选列表和结果数组，都是O(n)级别。

Go完整代码如下：

package main import (     "fmt"     "slices" ) // 预处理交替排列的方案数 var f = []int{1} func init() {     for i := 1; f[len(f)-1] < 1e15; i++ {         f = append(f, f[len(f)-1]*i)         f = append(f, f[len(f)-1]*i)     } } func permute(n int, K int64) []int {     // k 改成从 0 开始，方便计算     k := int(K - 1)     if n < len(f) && k >= f[n]*(2-n%2) { // n 是偶数的时候，方案数乘以 2         returnnil     }     // cand 表示剩余未填入 ans 的数字     // cand[0] 保存偶数，cand[1] 保存奇数     cand := [2][]int{}     for i := 2; i <= n; i += 2 {         cand[0] = append(cand[0], i)     }     for i := 1; i <= n; i += 2 {         cand[1] = append(cand[1], i)     }     ans := make([]int, n)     parity := 1// 当前要填入 ans[i] 的数的奇偶性     for i := range n {         j := 0         if n-1-i < len(f) {             // 比如示例 1，按照第一个数分组，每一组的大小都是 size=2             // 知道 k 和 size 就知道我们要去哪一组             size := f[n-1-i]             j = k / size // 去第 j 组             k %= size             // n 是偶数的情况，第一个数既可以填奇数又可以填偶数，要特殊处理             if n%2 == 0 && i == 0 {                 parity = 1 - j%2                 j /= 2             }         } // else j=0，在 n 很大的情况下，只能按照 1,2,3,... 的顺序填         ans[i] = cand[parity][j]         cand[parity] = slices.Delete(cand[parity], j, j+1)         parity ^= 1// 下一个数的奇偶性     }     return ans } func main() {     n := 4     k := int64(6)     result := permute(n, k)     fmt.Println(result) } 

Python完整代码如下：

# -*-coding:utf-8-*- import math # 预处理交替排列的方案数 f = [1] # 初始化f数组，直到最后一个元素超过1e15 while f[-1] < 1015:     i = len(f) // 2 + 1     f.append(f[-1] * i)     iflen(f) % 2 == 0:         f.append(f[-1] * i) def permute(n, K):     k = int(K - 1)  # k改为从0开始，方便计算     # 检查k是否超出范围（注意n为偶数时方案数乘以2）     if n < len(f) and k >= f[n] * (2 - n % 2):         return None     # cand[0]保存偶数，cand[1]保存奇数     cand = [[], []]     for i in range(2, n+1, 2):         cand[0].append(i)     for i in range(1, n+1, 2):         cand[1].append(i)          ans = [0] * n     parity = 1  # 当前要填入ans[i]的数的奇偶性（1表示奇数，0表示偶数）     for i in range(n):         j = 0         if n - 1 - i < len(f):             size = f[n - 1 - i]             j = k // size  # 去第j组             k %= size             # n是偶数的情况，第一个数既可以填奇数又可以填偶数，要特殊处理             if n % 2 == 0 and i == 0:                 parity = 1 - (j % 2)                 j //= 2         # 从候选列表中取出第j个元素         ans[i] = cand[parity][j]         del cand[parity][j]         parity ^= 1  # 切换奇偶性          return ans # 测试示例 if __name__ == "__main__":     n = 4     k = 6     result = permute(n, k)     print(result)  

·

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大大架构师每日一题”，让 Go 语言和算法助力您的职业发展

·