全排列IV

题目描述

给定两个整数 n 和 k。一个交替排列是指由前 n 个正整数组成的排列，且任意相邻两个元素不都为奇数或不都为偶数（即奇偶交替）。

返回按字典序排序后的第 k 个交替排列。如果有效的交替排列少于 k 个，则返回空列表 []。（注意输出格式，逗号和下一个数字之间有空格）

输入

一行，包含两个整数 n 和 k，以空格分隔。

输出

输出一个整数列表，表示第 k 个交替排列。如果不存在，输出 []。

样例

提示

• 1 \le n \le 100
• 1 \le k \le 10^{15}

样例解释 1

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

1. [1, 2, 3, 4]
2. [1, 4, 3, 2]
3. [2, 1, 4, 3]
4. [2, 3, 4, 1]
5. [3, 2, 1, 4]
6. [3, 4, 1, 2] ← 第 6 个

样例解释 2

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

1. [1, 2, 3]
2. [3, 2, 1] ← 第 2 个

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

1. [1, 2]
2. [2, 1]

只有 2 个交替排列，但 k = 3 超出了范围，因此返回空列表 []。

来源

leetcode