【华为OD-E卷 - 第k个排列 100分（python、java、c++、js、c）】 ...

【华为OD-E卷 - 第k个排列 100分（python、java、c++、js、c）】

标题

给定参数 n，从 1 到 n 会有 n 个整数：1,2,3,…,n, 这 n 个数字共有 n! 种排列。
按巨细顺序升序列出全部排列的情况，并一一标记，当 n = 3 时,全部排列如下:
“123” “132” “21
3
” “231” “312” “321
” 给定 n 和 k，返回第 k 个排列
输入描述

• 输入两行，第一行为 n，第二行为 k，
  

给定 n 的范围是[1, 9], 给定 k 的范围是[1, n!]
输出描述

• 输出排在第 k 位置的数字
  

用例

用例一：

输入：

1. 3
2. 3

复制代码

输出：

1. 21
2. 3

复制代码

用例二：

输入：

1. 2
2. 2

复制代码

输出：

1. 21

复制代码

python解法

• 解题思绪：
  
• 该代码的目的是解决排列组合中的第 k 个排列题目（即字典序第 k 小的排列）。题目描述是：给定正整数 n 和 k，返回从 [1, 2, …, n] 这些数字组成的全部排列中按字典序排列的第 k 个排列。
  

重要思绪：
使用阶乘数组：通过预盘算阶乘（factorial），快速确定某一位数字对应的索引范围。
按位置逐位构造排列：
确定第 i 位数字时，根据当前剩余排列数量可以盘算该位应该选取的数字。
从剩余数字中取出对应的数字，并从候选数字列表中移除。
递归更新剩余的索引值 k：
盘算余数，缩小题目规模，继续处理剩余的数字

1. n = int(input())  # 输入 n，表示排列的长度
2. k = int(input())  # 输入 k，表示需要找的第 k 个排列
4. # 初始化数字数组 [1, 2, ..., n]
5. numbers = [i + 1 for i in range(n)]
7. # 计算阶乘数组，用于快速确定当前数字的索引范围
8. factorial = [1] * (n + 1)
9. for i in range(2, n + 1):
10.     factorial[i] = factorial[i - 1] * i
12. # 初始化结果数组，用于存储最终的排列结果
13. result = []
15. # 因为索引从 0 开始，所以 k 减 1
16. k -= 1
18. # 遍历每一位，逐步确定每一位数字
19. for i in range(1, n + 1):
20.     # 计算当前位需要选择的数字索引
21.     index = k // factorial[n - i]
22.    
23.     # 将该数字添加到结果数组中
24.     result.append(str(numbers[index]))
25.    
26.     # 从候选数字中移除已选择的数字
27.     numbers.pop(index)
28.    
29.     # 更新 k 的值，缩小问题规模
30.     k %= factorial[n - i]
32. # 将结果数组拼接成字符串并输出
33. print("".join(result))

复制代码

java解法

• 解题思绪
  
• 目的是找到 [1, 2, …, n] 的全部排列中，按字典序排序后的第 k 个排列。解决方式与 Python 版本相似，采用递归的方法逐步构造结果。
  

重要步调：
使用阶乘的性质确定排列范围：
对于长度为 n 的排列，前 n-1 位的排列总数为 (n-1)!。
根据 (k-1) / (n-1)! 可以盘算出当前排列的起始数字的索引。
递归天生排列：
每次选定一个数字，将其从候选列表中移除。
根据剩余的 k 值，递归处理剩下的数字。
拼接结果：
每次递归选出的数字依次拼接，终极形成完整的排列。

1. import java.util.ArrayList;
2. import java.util.List;
3. import java.util.Scanner;
5. public class Main {
6.     public static void main(String[] args) {
7.         Scanner sc = new Scanner(System.in); // 创建输入对象
8.         int n = sc.nextInt(); // 输入 n，表示排列的长度
9.         int k = sc.nextInt(); // 输入 k，表示需要找的第 k 个排列
10.         List<Integer> nums = new ArrayList<>(); // 初始化数字列表 [1, 2, ..., n]
11.         for (int i = 1; i <= n; i++) nums.add(i);
12.         // 调用函数获取第 k 个排列并输出
13.         System.out.println(getPermutation(nums, k));
14.     }
16.     /**
17.      * 获取第 k 个排列
18.      * @param nums 候选数字列表
19.      * @param k    第 k 个排列（从 1 开始）
20.      * @return     第 k 个排列的字符串
21.      */
22.     public static String getPermutation(List<Integer> nums, int k) {
23.         // 如果列表为空，返回空字符串（递归终止条件）
24.         if (nums.size() == 0) return "";
25.         int n = nums.size(); // 当前列表的长度
26.         int f = factorial(n - 1); // 计算 (n-1)!，用于确定当前数字的范围
27.         int index = (k - 1) / f; // 确定当前位数字的索引
28.         int chosen = nums.remove(index); // 从候选数字列表中移除选择的数字
29.         k = k - index * f; // 更新 k，处理剩余部分
30.         // 返回当前选择的数字和剩余数字的排列结果
31.         return chosen + getPermutation(nums, k);
32.     }
34.     /**
35.      * 计算 n 的阶乘
36.      * @param n 非负整数
37.      * @return  n 的阶乘
38.      */
39.     public static int factorial(int n) {
40.         int result = 1; // 初始化结果为 1
41.         for (int i = 2; i <= n; i++) result *= i; // 从 2 开始累乘到 n
42.         return result;
43.     }
44. }

复制代码

C++解法

• 解题思绪
  
• 
  

1. 更新中

复制代码

C解法

• 解题思绪
  
• 
  

1. 更新中

复制代码

JS解法

• 解题思绪
  
• 问标题标是找到从 [1, 2, …, n] 这些数字中天生的全部排列中，按字典序第 k 小的排列。代码使用了贪心算法结合数学分析来高效解决该题目。
  

核心思绪：
使用阶乘的性质分割排列范围：
如果第一个数字固定为某值，那么剩下的排列数是 (n-1)!。
使用 k / (n-1)! 可以快速确定当前位的数字是哪一个。
动态更新数字列表：
每次确定一位数字后，将其从候选数字列表中移除。
逐步缩小题目规模：
更新 k 的值为当前范围内的余数，递归处理剩余的排列题目。
边界处理：
当数字列表为空时，递归终止

1. const readline = require('readline'); // 引入 readline 模块处理标准输入输出
2. const rl = readline.createInterface({
3.     input: process.stdin,
4.     output: process.stdout
5. });
7. rl.on('line', (input) => {
8.     // 处理输入，第一行为 n，第二行为 k
9.     if (!global.n) {
10.         global.n = parseInt(input.trim()); // 读取 n
11.     } else {
12.         global.k = parseInt(input.trim()); // 读取 k
13.         console.log(getKthPermutation(global.n, global.k)); // 输出第 k 个排列
14.         rl.close(); // 关闭输入流
15.     }
16. });
18. /**
19. * 获取第 k 个排列
20. * @param {number} n - 数字范围 1 到 n
21. * @param {number} k - 第 k 个排列（从 1 开始）
22. * @return {string} 返回第 k 个排列的字符串
23. */
24. function getKthPermutation(n, k) {
25.     let factorials = [1]; // 用于存储阶乘值
26.     let nums = []; // 候选数字列表
28.     // 初始化阶乘数组和候选数字列表
29.     for (let i = 1; i <= n; i++) {
30.         factorials[i] = factorials[i - 1] * i; // 计算并存储 i 的阶乘
31.         nums.push(i); // 将数字 i 加入候选数字列表
32.     }
34.     k--; // 将 k 转换为从 0 开始的索引
35.     let result = ''; // 存储最终结果的字符串
37.     // 从高位到低位依次确定每一位数字
38.     for (let i = n; i > 0; i--) {
39.         // 确定当前位数字的索引
40.         let idx = Math.floor(k / factorials[i - 1]);
41.         result += nums[idx]; // 将选定的数字添加到结果字符串中
42.         nums.splice(idx, 1); // 从候选数字列表中移除该数字
43.         k %= factorials[i - 1]; // 更新 k 的值为余数
44.     }
46.     return result; // 返回最终结果
47. }

复制代码

注意：

如果发现代码有用例覆盖不到的情况，接待反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，接待点赞/收藏

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。