当前位置：首页 > news >正文

华为OD机试真题---第k个排列

news 2025/5/6 4:48:46

针对华为OD机试真题中的“第k个排列”问题，以下是对题目的详细解析及解答方法：

题目描述

给定参数n，从1到n会有n个整数：1, 2, 3, …, n。这n个数字共有n!种排列。按大小顺序升序列出所有排列的情况，并一一标记。给定n和k，返回第k个排列。

输入与输出

输入：
1. 第一行为n，给定n的范围是[1, 9]。
2. 第二行为k，给定k的范围是[1, n!]。
输出：
- 输出排在第k位置的数字序列。

示例

示例1：
- 输入：3 3
- 输出：213
- 说明：3的排列有123, 132, 213, …, 那么第三位置就是213。
示例2：
- 输入：2 2
- 输出：21
- 说明：2的排列有12, 21，那么第二位置就是21。

解题思路

阶乘数组：首先，我们可以预计算一个阶乘数组，其中factorial[i]表示i的阶乘。这个数组将帮助我们确定每个数字在排列中的“组”位置。
确定每一位的数字：从最高位（最左边的数字）开始，我们可以通过将k除以(n-1)!来确定当前位的数字。具体来说，k / (n-1)!的商表示当前位的数字在1到n中的位置（注意要减1，因为数组是从0开始的），而余数则用于确定下一位的数字。
更新k值：在确定当前位的数字后，我们需要更新k值为余数，并继续处理下一位，直到所有位都被确定。

代码实现（Java）

package cn.gov.test.gt4.swjggl.leetcode;import org.slf4j.Logger;
import org.slf4j.LoggerFactory;import java.util.Arrays;
import java.util.Scanner;public class KthPermutation {private static final Logger log = LoggerFactory.getLogger(KthPermutation.class);public static void main(String[] args) {// 创建Scanner对象以读取命令行输入Scanner scanner = new Scanner(System.in);// 读取整数n，表示数字的范围int n = scanner.nextInt();// 读取整数k，表示排列的索引（从1开始）int k = scanner.nextInt();// 关闭Scanner对象scanner.close();// 生成从1到n的数字数组int[] nums = new int[n];for (int i = 0; i < n; i++) {nums[i] = i + 1;}// 从最高位开始确定每一位的数字，并同时移除已使用的数字int[] result = new int[n];k--; // 转换为从0开始的索引for (int i = 0; i < n; i++) {// 计算剩余元素的阶乘，用于确定当前位的数字int factorial = 1;for (int j = 1; j <= n - i - 1; j++) {factorial *= j;}// 确定当前位的数字（从0开始索引）int index = k / factorial;// 存储数字result[i] = nums[index];// 将已使用的数字从nums数组中移除（通过覆盖的方式）for (int j = index; j < n - 1; j++) {nums[j] = nums[j + 1];}// 更新k值为在当前“缩小”后的数组中的偏移量（仍然是从0开始索引）k %= factorial;}// 输出结果数组for (int num : result) {System.out.print(num);}}
}

**若想要打印出排列组合：**

// 打印出从1到n的所有数字的排列组合public static void printAllPermutations(int[] nums) {if (nums == null || nums.length == 0) {return;}boolean[] used = new boolean[nums.length]; // 标记数字是否已被使用printPermutations(nums, used, new StringBuilder());}// 递归打印排列组合的辅助方法private static void printPermutations(int[] nums, boolean[] used, StringBuilder current) {if (current.length() == nums.length) {// 当current字符串的长度等于nums数组的长度时，说明已经生成了一个完整的排列log.info(current.toString());return;}for (int i = 0; i < nums.length; i++) {if (!used[i]) {// 如果当前数字还没有被使用过used[i] = true; // 标记为已使用current.append(nums[i]); // 将数字添加到当前排列中// 递归调用，继续生成下一个位置的数字printPermutations(nums, used, current);// 回溯：移除刚刚添加的数字，并标记为未使用current.deleteCharAt(current.length() - 1);used[i] = false;}}}