Hard

题目描述

给定两个整数 n 和 k，交替排列是前 n 个正整数的一个排列，使得没有两个相邻元素都是奇数或都是偶数。

返回按字典序排序的第 k 个交替排列。如果有效的交替排列少于 k 个，则返回空列表。

示例 1：

输入：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]。

示例 2：

输入：n = 3, k = 2
输出：[3,2,1]
解释：
[1, 2, 3] 的按字典序排序的交替排列有：
[1, 2, 3]
[3, 2, 1] ← 第 2 个排列
因为 k = 2，我们返回 [3, 2, 1]。

示例 3：

输入：n = 2, k = 3
输出：[]
解释：
[1, 2] 的按字典序排序的交替排列有：
[1, 2]
[2, 1]
只有 2 个交替排列，但 k = 3，超出范围。因此返回空列表 []。

约束条件：

  • 1 <= n <= 100
  • 1 <= k <= 10^15

提示：

  • 如果 n 是奇数，第一个数必须是奇数。
  • 如果 n 是偶数，第一个数可以是奇数或偶数。
  • 从小到大放置每个数字，并从 k 中减去排列数。
  • 排列数可以用阶乘计算。

解题思路

这道题要求找到第 k 个交替排列，关键是理解交替排列的规律和如何直接构造第 k 个排列而不枚举所有排列。

核心思路：

  1. 交替排列规律：相邻元素的奇偶性必须不同。如果 n 是奇数，第一个位置必须是奇数；如果 n 是偶数，第一个位置可以是奇数或偶数。

  2. 直接构造法：使用类似康托展开的思想，对于每个位置，计算以当前可选数字开头的有效排列数量。通过比较这个数量与剩余的 k 值来确定当前位置应该选择哪个数字。

  3. 计算排列数：对于交替排列，我们需要分别维护奇数和偶数的可用数字集合。在每个位置，根据奇偶性要求选择对应集合中的数字，然后计算剩余数字能构成的排列数。

  4. 优化计算：预计算阶乘值，避免重复计算。同时要注意处理 k 超出总排列数的情况。

算法步骤：

  • 分离奇数和偶数到两个数组
  • 预计算阶乘值
  • 计算总的交替排列数，判断 k 是否有效
  • 逐位确定排列：对于每个位置，根据奇偶性要求从对应数组中选择数字
  • 计算以当前数字开头的排列数，更新 k 值

代码实现

class Solution {
public:
    vector<int> permute(int n, long long k) {
        vector<int> odds, evens;
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 1) odds.push_back(i);
            else evens.push_back(i);
        }
        
        vector<long long> fact(n + 1, 1);
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i-1] * i;
        }
        
        // Calculate total valid permutations
        long long total = 0;
        if (n % 2 == 1) {
            // Must start with odd
            total = fact[odds.size()] * fact[evens.size()];
        } else {
            // Can start with odd or even
            total = 2 * fact[odds.size()] * fact[evens.size()];
        }
        
        if (k > total) return {};
        
        vector<int> result;
        k--; // Convert to 0-indexed
        
        for (int pos = 0; pos < n; pos++) {
            bool needOdd = (pos % 2 == 0 && n % 2 == 1) || (pos % 2 == 1 && n % 2 == 0);
            
            if (needOdd) {
                long long permsPerChoice = fact[odds.size() - 1] * fact[evens.size()];
                int choice = k / permsPerChoice;
                result.push_back(odds[choice]);
                odds.erase(odds.begin() + choice);
                k %= permsPerChoice;
            } else {
                long long permsPerChoice = fact[odds.size()] * fact[evens.size() - 1];
                int choice = k / permsPerChoice;
                result.push_back(evens[choice]);
                evens.erase(evens.begin() + choice);
                k %= permsPerChoice;
            }
        }
        
        return result;
    }
};

class Solution:
    def permute(self, n: int, k: int) -> List[int]:
        odds = [i for i in range(1, n + 1) if i % 2 == 1]
        evens = [i for i in range(1, n + 1) if i % 2 == 0]
        
        # Precompute factorials
        fact = [1] * (n + 1)
        for i in range(1, n + 1):
            fact[i] = fact[i-1] * i
        
        # Calculate total valid permutations
        if n % 2 == 1:
            total = fact[len(odds)] * fact[len(evens)]
        else:
            total = 2 * fact[len(odds)] * fact[len(evens)]
        
        if k > total:
            return []
        
        result = []
        k -= 1  # Convert to 0-indexed
        
        for pos in range(n):
            need_odd = (pos % 2 == 0 and n % 2 == 1) or (pos % 2 == 1 and n % 2 == 0)
            
            if need_odd:
                perms_per_choice = fact[len(odds) - 1] * fact[len(evens)]
                choice = k // perms_per_choice
                result.append(odds[choice])
                odds.pop(choice)
                k %= perms_per_choice
            else:
                perms_per_choice = fact[len(odds)] * fact[len(evens) - 1]
                choice = k // perms_per_choice
                result.append(evens[choice])
                evens.pop(choice)
                k %= perms_per_choice
        
        return result

public class Solution {
    public int[] Permute(int n, long k) {
        var odds = new List<int>();
        var evens = new List<int>();
        
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 1) odds.Add(i);
            else evens.Add(i);
        }
        
        var fact = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i-1] * i;
        }
        
        // Calculate total valid permutations
        long total;
        if (n % 2 == 1) {
            total = fact[odds.Count] * fact[evens.Count];
        } else {
            total = 2 * fact[odds.Count] * fact[evens.Count];
        }
        
        if (k > total) return new int[0];
        
        var result = new List<int>();
        k--; // Convert to 0-indexed
        
        for (int pos = 0; pos < n; pos++) {
            bool needOdd = (pos % 2 == 0 && n % 2 == 1) || (pos % 2 == 1 && n % 2 == 0);
            
            if (needOdd) {
                long permsPerChoice = fact[odds.Count - 1] * fact[evens.Count];
                int choice = (int)(k / permsPerChoice);
                result.Add(odds[choice]);
                odds.RemoveAt(choice);
                k %= permsPerChoice;
            } else {
                long permsPerChoice = fact[odds.Count] * fact[evens.Count - 1];
                int choice = (int)(k / permsPerChoice);
                result.Add(evens[choice]);
                evens.RemoveAt(choice);
                k %= permsPerChoice;
            }
        }
        
        return result.ToArray();
    }
}

var permute = function(n, k) {
    const odds = [];
    const evens = [];
    
    for (let i = 1; i <= n; i++) {
        if (i % 2 === 1) odds.push(i);
        else evens.push(i);
    }
    
    function factorial(num) {
        let result = 1n;
        for (let i = 2; i <= num; i++) {
            result *= BigInt(i);
        }
        return result;
    }
    
    const oddCount = odds.length;
    const evenCount = evens.length;
    
    // Calculate total valid permutations
    let totalPerms = 0n;
    if (oddCount > 0) {
        totalPerms += factorial(oddCount) * factorial(evenCount);
    }
    if (evenCount > 0) {
        totalPerms += factorial(oddCount) * factorial(evenCount);
    }
    
    if (BigInt(k) > totalPerms) return [];
    
    k = BigInt(k) - 1n; // Convert to 0-indexed
    
    // Determine if we start with odd or even
    const oddFirstPerms = factorial(oddCount) * factorial(evenCount);
    let startWithOdd = true;
    
    if (k >= oddFirstPerms) {
        startWithOdd = false;
        k -= oddFirstPerms;
    }
    
    let availableOdds = [...odds];
    let availableEvens = [...evens];
    let result = [];
    let needOdd = startWithOdd;
    
    for (let pos = 0; pos < n; pos++) {
        if (needOdd) {
            const remaining = availableOdds.length - 1;
            const permsPerChoice = factorial(remaining) * factorial(availableEvens.length);
            const choiceIndex = Number(k / permsPerChoice);
            
            result.push(availableOdds[choiceIndex]);
            availableOdds.splice(choiceIndex, 1);
            k %= permsPerChoice;
        } else {
            const remaining = availableEvens.length - 1;
            const permsPerChoice = factorial(remaining) * factorial(availableOdds.length);
            const choiceIndex = Number(k / permsPerChoice);
            
            result.push(availableEvens[choiceIndex]);
            availableEvens.splice(choiceIndex, 1);
            k %= permsPerChoice;
        }
        needOdd = !needOdd;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n²)
空间复杂度O(n)

时间复杂度分析：预计算阶乘需要 O(n)，主循环执行 n 次，每次需要从数组中删除元素，最坏情况下需要 O(n)，总体为 O(n²)。 空间复杂度分析：需要存储奇数数组、偶数数组、阶乘数组和结果数组，总空间为 O(n)。

相关题目