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

1 <= n <= 100。

1 <= k <= 1000000000000000。

输入：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）

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

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

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

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

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

2. 输入验证和初始化

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

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

o 创建两个候选列表：

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

3. 构建排列过程

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

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

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

4. 返回结果

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

特殊情况处理

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

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

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

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

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

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

o 主循环（n次迭代）：

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

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

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

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

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

o 其他变量：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] < 10**15:
    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 语言和算法助力您的职业发展

·