第k个排列 - 华为OD统一考试(E卷)

2024华为OD机试（E卷+D卷+C卷）最新题库【超值优惠】Java/Python/C++合集

华为od机试

题目描述

给定参数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 math

def 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 // fact
        result.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;
}