Hard

题目描述

集合 [1, 2, 3, …, n] 包含总共 n! 个唯一排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"

给定 n 和 k，返回第 k 个排列。

示例 1:

输入：n = 3, k = 3
输出："213"

示例 2:

输入：n = 4, k = 9
输出："2314"

示例 3:

输入：n = 3, k = 1
输出："123"

提示:

  • 1 <= n <= 9
  • 1 <= k <= n!

解题思路

这道题可以用数学方法巧妙求解，避免枚举所有排列。

核心思路： 对于n个数的排列，第一个位置有n种选择，每种选择后面有(n-1)!种排列。因此我们可以通过除法确定第一个数字，通过取余确定在剩余数字中的位置。

具体算法：

  1. 预计算阶乘值，用于快速计算每个位置的排列数
  2. 维护一个可选数字列表 [1,2,…,n]
  3. 对每个位置：
    • 计算当前位置每个数字对应的排列组数：(n-1)!
    • 通过 (k-1) // (n-1)! 确定当前位置应该选择第几个数字
    • 从可选列表中取出该数字，加入结果
    • 更新k值：k = (k-1) % (n-1)! + 1
    • 继续处理下一个位置

为什么用k-1： 因为排列编号从1开始，而数组索引从0开始，需要转换。

**推荐解法：**数学计算法，时间复杂度O(n²)，空间复杂度O(n)。

代码实现

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> factorial(n, 1);
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
        
        vector<int> nums;
        for (int i = 1; i <= n; i++) {
            nums.push_back(i);
        }
        
        string result = "";
        k--; // 转换为0-based索引
        
        for (int i = n; i >= 1; i--) {
            int idx = k / factorial[i - 1];
            result += to_string(nums[idx]);
            nums.erase(nums.begin() + idx);
            k %= factorial[i - 1];
        }
        
        return result;
    }
};

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        import math
        
        factorial = [1] * n
        for i in range(1, n):
            factorial[i] = factorial[i - 1] * i
        
        nums = list(range(1, n + 1))
        result = []
        k -= 1  # 转换为0-based索引
        
        for i in range(n, 0, -1):
            idx = k // factorial[i - 1]
            result.append(str(nums.pop(idx)))
            k %= factorial[i - 1]
        
        return ''.join(result)

public class Solution {
    public string GetPermutation(int n, int k) {
        int[] factorial = new int[n];
        factorial[0] = 1;
        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
        
        List<int> nums = new List<int>();
        for (int i = 1; i <= n; i++) {
            nums.Add(i);
        }
        
        StringBuilder result = new StringBuilder();
        k--; // 转换为0-based索引
        
        for (int i = n; i >= 1; i--) {
            int idx = k / factorial[i - 1];
            result.Append(nums[idx]);
            nums.RemoveAt(idx);
            k %= factorial[i - 1];
        }
        
        return result.ToString();
    }
}

var getPermutation = function(n, k) {
    const factorial = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        factorial[i] = factorial[i - 1] * i;
    }
    
    const nums = [];
    for (let i = 1; i <= n; i++) {
        nums.push(i);
    }
    
    let result = "";
    k--; // 转换为0-based索引
    
    for (let i = n; i >= 1; i--) {
        const idx = Math.floor(k / factorial[i - 1]);
        result += nums[idx];
        nums.splice(idx, 1);
        k %= factorial[i - 1];
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要n轮循环，每轮删除元素需要O(n)时间
空间复杂度O(n)需要存储阶乘数组和候选数字列表

相关题目