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）

• 初始化一个阶乘数组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
		return nil
	}

	// 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)
    if len(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)