【华为OD-E卷 - 第k个排列 100分（python、java、c++、js、c）】
题目
给定参数 n，从 1 到 n 会有 n 个整数：1,2,3,…,n, 这 n 个数字共有 n! 种排列。
按大小顺序升序列出所有排列的情况，并一一标记，当 n = 3 时,所有排列如下:
“123” “132” “213” “231” “312” “321” 给定 n 和 k，返回第 k 个排列
输入描述
- 输入两行，第一行为 n，第二行为 k，
给定 n 的范围是[1, 9], 给定 k 的范围是[1, n!]
输出描述
- 输出排在第 k 位置的数字
用例
用例一：
输入：
3
3
输出：
213
用例二：
输入：
2
2
输出：
21
python解法
- 解题思路：
- 该代码的目标是解决排列组合中的第 k 个排列问题（即字典序第 k 小的排列）。问题描述是：给定正整数 n 和 k，返回从 [1, 2, …, n] 这些数字组成的所有排列中按字典序排列的第 k 个排列。
主要思路：
使用阶乘数组：通过预计算阶乘（factorial），快速确定某一位数字对应的索引范围。
按位置逐位构造排列：
确定第 i 位数字时，根据当前剩余排列数量可以计算该位应该选取的数字。
从剩余数字中取出对应的数字，并从候选数字列表中移除。
递归更新剩余的索引值 k：
计算余数，缩小问题规模，继续处理剩余的数字
n = int(input()) # 输入 n，表示排列的长度
k = int(input()) # 输入 k，表示需要找的第 k 个排列
# 初始化数字数组 [1, 2, ..., n]
numbers = [i + 1 for i in range(n)]
# 计算阶乘数组，用于快速确定当前数字的索引范围
factorial = [1] * (n + 1)
for i in range(2, n + 1):
factorial[i] = factorial[i - 1] * i
# 初始化结果数组，用于存储最终的排列结果
result = []
# 因为索引从 0 开始，所以 k 减 1
k -= 1
# 遍历每一位，逐步确定每一位数字
for i in range(1, n + 1):
# 计算当前位需要选择的数字索引
index = k // factorial[n - i]
# 将该数字添加到结果数组中
result.append(str(numbers[index]))
# 从候选数字中移除已选择的数字
numbers.pop(index)
# 更新 k 的值，缩小问题规模
k %= factorial[n - i]
# 将结果数组拼接成字符串并输出
print("".join(result))
java解法
- 解题思路
- 目标是找到 [1, 2, …, n] 的所有排列中，按字典序排序后的第 k 个排列。解决方式与 Python 版本相似，采用递归的方法逐步构造结果。
主要步骤：
利用阶乘的性质确定排列范围：
对于长度为 n 的排列，前 n-1 位的排列总数为 (n-1)!。
根据 (k-1) / (n-1)! 可以计算出当前排列的起始数字的索引。
递归生成排列：
每次选定一个数字，将其从候选列表中移除。
根据剩余的 k 值，递归处理剩下的数字。
拼接结果：
每次递归选出的数字依次拼接，最终形成完整的排列。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); // 创建输入对象
int n = sc.nextInt(); // 输入 n，表示排列的长度
int k = sc.nextInt(); // 输入 k，表示需要找的第 k 个排列
List<Integer> nums = new ArrayList<>(); // 初始化数字列表 [1, 2, ..., n]
for (int i = 1; i <= n; i++) nums.add(i);
// 调用函数获取第 k 个排列并输出
System.out.println(getPermutation(nums, k));
}
/**
* 获取第 k 个排列
* @param nums 候选数字列表
* @param k 第 k 个排列（从 1 开始）
* @return 第 k 个排列的字符串
*/
public static String getPermutation(List<Integer> nums, int k) {
// 如果列表为空，返回空字符串（递归终止条件）
if (nums.size() == 0) return "";
int n = nums.size(); // 当前列表的长度
int f = factorial(n - 1); // 计算 (n-1)!，用于确定当前数字的范围
int index = (k - 1) / f; // 确定当前位数字的索引
int chosen = nums.remove(index); // 从候选数字列表中移除选择的数字
k = k - index * f; // 更新 k，处理剩余部分
// 返回当前选择的数字和剩余数字的排列结果
return chosen + getPermutation(nums, k);
}
/**
* 计算 n 的阶乘
* @param n 非负整数
* @return n 的阶乘
*/
public static int factorial(int n) {
int result = 1; // 初始化结果为 1
for (int i = 2; i <= n; i++) result *= i; // 从 2 开始累乘到 n
return result;
}
}
C++解法
- 解题思路
更新中
C解法
更新中
JS解法
核心思路：
使用阶乘的性质分割排列范围：
如果第一个数字固定为某值，那么剩下的排列数是 (n-1)!。
利用 k / (n-1)! 可以快速确定当前位的数字是哪一个。
动态更新数字列表：
每次确定一位数字后，将其从候选数字列表中移除。
逐步缩小问题规模：
更新 k 的值为当前范围内的余数，递归处理剩余的排列问题。
边界处理：
当数字列表为空时，递归终止
const readline = require('readline'); // 引入 readline 模块处理标准输入输出
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
rl.on('line', (input) => {
// 处理输入，第一行为 n，第二行为 k
if (!global.n) {
global.n = parseInt(input.trim()); // 读取 n
} else {
global.k = parseInt(input.trim()); // 读取 k
console.log(getKthPermutation(global.n, global.k)); // 输出第 k 个排列
rl.close(); // 关闭输入流
}
});
/**
* 获取第 k 个排列
* @param {number} n - 数字范围 1 到 n
* @param {number} k - 第 k 个排列（从 1 开始）
* @return {string} 返回第 k 个排列的字符串
*/
function getKthPermutation(n, k) {
let factorials = [1]; // 用于存储阶乘值
let nums = []; // 候选数字列表
// 初始化阶乘数组和候选数字列表
for (let i = 1; i <= n; i++) {
factorials[i] = factorials[i - 1] * i; // 计算并存储 i 的阶乘
nums.push(i); // 将数字 i 加入候选数字列表
}
k--; // 将 k 转换为从 0 开始的索引
let result = ''; // 存储最终结果的字符串
// 从高位到低位依次确定每一位数字
for (let i = n; i > 0; i--) {
// 确定当前位数字的索引
let idx = Math.floor(k / factorials[i - 1]);
result += nums[idx]; // 将选定的数字添加到结果字符串中
nums.splice(idx, 1); // 从候选数字列表中移除该数字
k %= factorials[i - 1]; // 更新 k 的值为余数
}
return result; // 返回最终结果
}
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏