组成最大数 - 华为OD统一考试(E卷)

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

题目描述

小组中每位都有一张卡片，卡片上是6位以内的正整数。将卡片连起来可以组成多种数字，计算组成的最大数字。

输入描述

,号分割的多个正整数字符串，不需要考虑非数字字符情况，小组最多25个人。

输出描述

最大的数字字符串

示例1

输入：

22,221

输出：

22221

说明： 将22和221组合成最大值的排列是22221。

示例2

输入：

4589,101,41425,9999

输出：

9999458941425101

说明： 将4589, 101, 41425, 9999组合成最大值的排列是9999458941425101。

题解

题目类型

这道题属于贪心算法类型的题目。题目的核心在于：如何通过将多个数字组合成一个字符串来形成尽可能大的数字。要做到这一点，需要通过贪心的思想，在每一步选择两个数字组合时，确保它们的拼接顺序能带来全局最优解。

解题思路

1. 字符串比较：首先，我们要确定如何将数字拼接在一起才能得到最大的数字。对于两个数字 a 和 b，我们可以比较 a + b 和 b + a 的结果。如果 a + b 大于 b + a，那么 a 应该排在 b 前面，反之亦然。
2. 排序：基于以上的比较规则，我们可以将输入的数字转换为字符串，然后按照上述规则对字符串数组进行排序。排序后的结果，拼接起来就是能形成的最大数字

代码大致描述

• Java: 使用 Arrays.sort() 方法自定义排序规则，利用 compareTo 比较字符串拼接后的字典序。最后将排好序的字符串数组拼接为最终结果。

• Python: 使用 sorted() 函数，并结合 cmp_to_key 进行自定义比较。自定义比较函数类似于 Java 中的 compareTo，比较两个数字拼接后的大小。

• C++: 使用 sort() 函数和自定义比较函数 compare，对字符串进行排序。排序后通过拼接得到最大的数字。

时间复杂度

排序是此问题的核心部分，排序的时间复杂度主要取决于比较函数的执行次数。假设输入有 n 个字符串，每个字符串的平均长度为 k：

• 比较操作的时间复杂度：比较两个字符串的时间复杂度为 O(k)，因为我们需要比较拼接后的两个字符串。
• 排序的时间复杂度：排序的总体复杂度是 O(n log n)，因此总体时间复杂度为 O(n k log n)。

空间复杂度

空间复杂度主要取决于存储中间结果的字符串数组：

• 额外存储空间：我们需要存储排序后的数组，因此空间复杂度为 O(n)，加上用于存储拼接结果的 O(n * k)，总的空间复杂度为 O(n k)。

总结

这道题属于经典的贪心算法题目，重点在于如何正确自定义字符串拼接的排序规则。通过对数字进行排序，并将排序结果拼接成字符串，可以得到最大可能的数字。

Java

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] nums = in.nextLine().split(",");

        // 排序规则，两个字符串拼接后比