LeetCode 60. 排列序列

Categories:

题目描述
思路分析
1. 解法一：阶乘数系统（推荐）
相似题目

题目描述

✅ 60. 排列序列

思路分析

解法一：阶乘数系统（推荐）

核心思路：

预计算 1..n 的阶乘。

使用 k-1 的阶乘数系统表示，逐位确定当前选择的数字。

每次从剩余数字列表中取第 index = k / (n-1)! 个。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示数字个数，列表删除为 O(n)。

空间复杂度：O(n)。

// 阶乘数系统构造第 k 个排列
class Solution {
    public String getPermutation(int n, int k) {
        int[] fact = new int[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i;
        }

        List<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            nums.add(i);
        }

        k--;
        StringBuilder sb = new StringBuilder();
        for (int i = n; i >= 1; i--) {
            int idx = k / fact[i - 1];
            k = k % fact[i - 1];
            sb.append(nums.get(idx));
            nums.remove(idx);
        }
        return sb.toString();
    }
}

import "strconv"

// 阶乘数系统构造第 k 个排列
func getPermutation(n int, k int) string {
	fact := make([]int, n+1)
	fact[0] = 1
	for i := 1; i <= n; i++ {
		fact[i] = fact[i-1] * i
	}

	nums := make([]int, 0, n)
	for i := 1; i <= n; i++ {
		nums = append(nums, i)
	}

	k--
	res := make([]byte, 0, n)
	for i := n; i >= 1; i-- {
		idx := k / fact[i-1]
		k = k % fact[i-1]

		// 将当前选择的数字拼接到结果
		res = append(res, strconv.Itoa(nums[idx])...)
		nums = append(nums[:idx], nums[idx+1:]...)
	}

	return string(res)
}

相似题目

题目	难度	考察点
46. 全排列	中等	回溯
47. 全排列 II	中等	回溯
31. 下一个排列	中等	排列
556. 下一个更大元素 III	中等	排列
60. 排列序列	中等	数学

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/17635354