华为OD机试E卷 - 第k个排列（Java & Python& JS & C++ & C ）

在编程竞赛和面试中，常常会遇到排列组合的相关问题。这类问题不仅考察我们对数据结构和算法的理解，还能测试我们的编程能力。在这篇文章中，我们将探讨如何找到集合中第k个排列的问题，并给出相应的Java、Python、JavaScript、C++和C语言的实现。

问题描述

给定一个正整数n，表示数字1到n的一个集合，和一个整数k，要求我们返回这个集合的第k个排列。注意，这里k是从1开始计数的。例如：

• 输入：n = 3, k = 3
• 输出："213"

思路与步骤

我们可以使用一种组合数学的方法来解决这个问题。具体步骤如下：

1. 计算阶乘：先预计算0到n-1的阶乘，因为这些阶乘的结果将用于判断每个数字在排列中的位置。
2. 构建数字列表：使用一个列表来存放从1到n的所有数字。
3. 构建第k个排列：我们从1到n依次选择数字，每次根据k值来确定当前位的数字，并更新k值和可用数字列表。

通过上面的过程，我们可以得到所需的排列。

代码示例

接下来看不同编程语言中的实现。

Java

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public String getPermutation(int n, int k) {
        List<Integer> numbers = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            numbers.add(i);
        }

        k--; // 转换为0-index
        StringBuilder sb = new StringBuilder();
        int[] factorial = new int[n];
        factorial[0] = 1;

        for (int i = 1; i < n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }

        for (int i = 0; i < n; i++) {
            int idx = k / factorial[n - 1 - i];
            sb.append(numbers.get(idx));
            numbers.remove(idx);
            k -= idx * factorial[n - 1 - i];
        }

        return sb.toString();
    }
}

Python

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        numbers = list(range(1, n + 1))
        k -= 1  # 转换为0-index
        factorial = [1] * n

        for i in range(1, n):
            factorial[i] = factorial[i - 1] * i

        permutation = []

        for i in range(n):
            idx = k // factorial[n - 1 - i]
            permutation.append(str(numbers[idx]))
            numbers.pop(idx)
            k %= factorial[n - 1 - i]

        return ''.join(permutation)

JavaScript

var getPermutation = function(n, k) {
    let numbers = Array.from({length: n}, (_, i) => i + 1);
    k--; // 转换为0-index
    let factorial = Array(n).fill(1);

    for (let i = 1; i < n; i++) {
        factorial[i] = factorial[i - 1] * i;
    }

    let permutation = '';

    for (let i = 0; i < n; i++) {
        let idx = Math.floor(k / factorial[n - 1 - i]);
        permutation += numbers[idx];
        numbers.splice(idx, 1);
        k %= factorial[n - 1 - i];
    }

    return permutation;
};

C++

#include <vector>
#include <string>

class Solution {
public:
    std::string getPermutation(int n, int k) {
        std::vector<int> numbers;
        for (int i = 1; i <= n; ++i) {
            numbers.push_back(i);
        }

        k--; // 转换为0-index
        std::vector<int> factorial(n);
        factorial[0] = 1;

        for (int i = 1; i < n; ++i) {
            factorial[i] = factorial[i - 1] * i;
        }

        std::string permutation;

        for (int i = 0; i < n; ++i) {
            int idx = k / factorial[n - 1 - i];
            permutation += std::to_string(numbers[idx]);
            numbers.erase(numbers.begin() + idx);
            k -= idx * factorial[n - 1 - i];
        }

        return permutation;
    }
};

C

#include <stdio.h>
#include <stdlib.h>

char* getPermutation(int n, int k) {
    int* numbers = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        numbers[i] = i + 1;
    }

    k--; // 转换为0-index
    int* factorial = (int*)malloc(n * sizeof(int));
    factorial[0] = 1;

    for (int i = 1; i < n; i++) {
        factorial[i] = factorial[i - 1] * i;
    }

    char* permutation = (char*)malloc((n + 1) * sizeof(char));
    permutation[n] = '\0'; // 字符串结束符

    for (int i = 0; i < n; i++) {
        int idx = k / factorial[n - 1 - i];
        permutation[i] = numbers[idx] + '0'; // 转为字符
        for (int j = idx; j < n - 1; j++) {
            numbers[j] = numbers[j + 1]; // 移动
        }
        k %= factorial[n - 1 - i];
    }

    free(numbers);
    free(factorial);
    return permutation;
}

总结

通过以上的代码示例，我们可以看到，不同编程语言在实现相同算法时的差异和共通之处。这个问题的涉及的关键点是组合数学和有效的数列操作，掌握了这些，你就能在面对类似问题时游刃有余。希望本文能够帮助你更好地理解如何解决排列相关的问题。