第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! 种排列。通过 数学方法 来求解，我们可以避免生成所有排列，直接通过数学推理一步步缩小范围，找到目标排列。

思路

1. 数学推导：
   • 每个位置的元素可以通过判断当前是第几组排列来决定。对于排列的第一位，有 n 种选择，而剩下的 n-1 位对应的排列数为 (n-1)!。
   • 比如 n=3，则有 3!=6 种排列，其中每两组排列会以 1 开头、2 开头、或者 3 开头。所以第一个位置的数字可以通过 k 来确定，依次缩小范围直到找出第 k 个排列。
2. 逐步计算：
   • 计算 (n-1)!，确定第一个数字的范围；
   • 更新 k 的值，并继续计算下一个位置的数字，直到生成完整排列。
3. 关键技巧：
   • 用一个数字列表存储所有可以选择的数字；
   • 根据 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 开始计数