第k个排列 - 华为OD统一考试(E卷)
2024华为OD机试(E卷+D卷+C卷)最新题库【超值优惠】Java/Python/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位置的数字。
示例1
输入:
3
3
输出:
213
说明:
3的排列有123 132 213...,那么第3位置的为213
示例2
输入:
2
2
输出:
21
说明:
2的排列有12 21,那么第2位置的为21
题解
这道题属于排列组合问题,需要找到第
k
个排列。给定数字n
,有n!
种排列。通过 数学方法 来求解,我们可以避免生成所有排列,直接通过数学推理一步步缩小范围,找到目标排列。思路
- 数学推导:
- 每个位置的元素可以通过判断当前是第几组排列来决定。对于排列的第一位,有
n
种选择,而剩下的n-1
位对应的排列数为(n-1)!
。- 比如
n=3
,则有3!=6
种排列,其中每两组排列会以1
开头、2
开头、或者3
开头。所以第一个位置的数字可以通过k
来确定,依次缩小范围直到找出第k
个排列。- 逐步计算:
- 计算
(n-1)!
,确定第一个数字的范围;- 更新
k
的值,并继续计算下一个位置的数字,直到生成完整排列。- 关键技巧:
- 用一个数字列表存储所有可以选择的数字;
- 根据
k
来选择当前的数字,并将其从候选列表中移除;- 每次计算第
i
位时,将k
减去已经完成的所有组数。时间复杂度
- 由于每次计算需要根据
(n-1)!
来确定当前数字,时间复杂度为O(n)
。
Java
import java.util.*;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
System.out.println(getPermutation(n, k));
}
public static String getPermutation(int n, int k) {
// 初始化可选数字列表
List<Integer> nums = new ArrayList<>();
for (int i = 1; i <= n; i++) {
nums.add(i);
}
StringBuilder result = new StringBuilder();
k--; // 转换为从 0 开始计数
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
华为OD机试题库题解2024 文章被收录于专栏
华为OD机考(CDE卷)题库(绝对都是原题),帮助你上岸华为(已经不少小伙伴成功上岸)。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题,随时解答。