第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 开始计数// 逐位确定排列int fact = 1;for (int i = 1; i < n; i++) {fact *= i;  // 计算 (n-1)!}for (int i = n; i > 0; i--) {// 确定当前位的索引int index = k / fact;result.append(nums.remove(index));// 更新 k 的值k %= fact;if (i > 1) {fact /= (i - 1);  // 计算新的 (i-2)!}}return result.toString();}
}

Python

import mathdef get_permutation(n, k):# 初始化可选数字列表nums = [str(i) for i in range(1, n + 1)]# 结果数组result = []# 将 k 转为从 0 开始计数k -= 1# 逐位确定排列for i in range(n, 0, -1):# 计算 (i-1)! 的值fact = math.factorial(i - 1)# 选择当前位的数字index = k // factresult.append(nums.pop(index))# 更新 k 的值k %= fact# 返回结果字符串return ''.join(result)# 输入处理
if __name__ == "__main__":n = int(input())k = int(input())# 输出第 k 个排列print(get_permutation(n, k))

C++

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;string getPermutation(int n, int k) {// 初始化可选数字列表vector<int> nums;for (int i = 1; i <= n; i++) {nums.push_back(i);}string result;k--;  // 转换为从 0 开始计数// 逐位确定排列int fact = 1;for (int i = 1; i < n; i++) {fact *= i;  // 计算 (n-1)!}for (int i = n; i > 0; i--) {// 确定当前位的索引int index = k / fact;result += to_string(nums[index]);nums.erase(nums.begin() + index);  // 从列表中移除该数字// 更新 k 的值k %= fact;if (i > 1) {fact /= (i - 1);  // 计算新的 (i-2)!}}return result;
}int main() {int n, k;cin >> n >> k;cout << getPermutation(n, k) << endl;return 0;
}