针对华为OD机试真题中的“第k个排列”问题,以下是对题目的详细解析及解答方法:
题目描述
给定参数n,从1到n会有n个整数:1, 2, 3, …, n。这n个数字共有n!种排列。按大小顺序升序列出所有排列的情况,并一一标记。给定n和k,返回第k个排列。
输入与输出
-
输入:
- 第一行为n,给定n的范围是[1, 9]。
- 第二行为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;
}
}
}
注意事项
- 数组索引:在Java中,数组索引是从0开始的,而题目中的排列是从1开始的。因此,在代码中需要注意这种差异,并进行适当的调整。
- 输入验证:虽然题目已经给出了n和k的取值范围,但在实际编程中,最好还是添加一些输入验证的代码来确保输入的有效性。
- 性能优化:由于n的取值范围较小(最多为9),上述实现已经足够高效。但如果n的取值范围更大,可能需要考虑更高效的算法或数据结构来优化性能。