E卷-最大值-(100分)

最大值

问题描述

给定一组非负整数，需要重新排列这些整数的顺序，将它们拼接成一个最大的整数。由于结果可能非常大，要求返回一个字符串而不是整数。

输入格式

输入包含一行，为空格分隔的若干个非负整数。

输出格式

输出一行，为重排后得到的最大整数，以字符串形式表示。

样例输入1

10 9

样例输出1

910

样例输入2

  3 30 34 5 9

样例输出2

9534330

样例解释

数据范围

• ，其中 是输入的整数个数。
• 输入的每个整数 。

题解

自定义排序

这道题目的关键在于如何正确地比较两个数字的拼接顺序。乍一看，我们可能会认为直接按照数字大小排序就可以了，但实际上这样做是不对的。

考虑一下 3 和 30 这两个数字。如果按照数字大小排序，我们会得到 330，但实际上 303 才是更大的数。这说明我们需要一个特殊的比较规则。

解决这个问题的关键是理解：对于两个数 a 和 b，如果 ab > ba，那么 a 应该排在 b 前面。这里的 ab 和 ba 指的是将 a 和 b 拼接成的数字。

具体来说，我们可以这样实现：

1. 将所有数字转换为字符串。
2. 定义一个比较函数，比较 a+b 和 b+a 的大小（这里的 + 表示字符串拼接）。
3. 使用这个比较函数对所有字符串进行排序。
4. 将排序后的字符串拼接起来，得到最终结果。

这个方法的时间复杂度是 O(nlogn)，主要来自排序的时间。对于给定的数据范围（n <= 100），这个复杂度是完全可以接受的。

需要注意的一个特殊情况是：如果输入全是 0，那么输出应该是 "0" 而不是 "00...0"。我们可以在最后检查一下，如果结果的第一个字符是 '0'，就直接返回 "0"。

参考代码

• Python

from functools import cmp_to_key

def largestNumber(nums):
    # 将数字转换为字符串
    nums = list(map(str, nums))
    
    # 定义比较函数
    def compare(a, b):
        if a + b > b + a:
            return -1
        elif a + b < b + a:
            return 1
        else:
            return 0
    
    # 使用自定义的比较函数进行排序
    nums.sort(key=cmp_to_key(compare))
    
    # 拼接结果
    result = ''.join(nums)
    
    # 处理特殊情况：如果结果全是0，应该返回"0"而不是"00...0"
    return "0" if result[0] == "0" else result

# 读取输入
nums = list(map(int, input().split()))

# 计算并输出结果
print(largestNumber(nums))

• C

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

// 比较函数，用于排序
int compare(const void* a, const void* b) {
    char ab[21], ba[21];
    sprintf(ab, "%d%d", *(int*)a, *(int*)b);
    sprintf(ba, "%d%d", *(int*)b, *(int*)a);
    return strcmp(ba, ab);  // 注意这里是ba和ab比较，为了降序排列
}

char* largestNumber(int* nums, int numsSize) {
    // 使用qsort进行排序
    qsort(nums, numsSize, sizeof(int), compare);
    
    // 计算结果字符串的最大可能长度
    int maxLen = numsSize * 10;
    char* result = (char*)malloc(maxLen + 1);
    result[0] = '\0';
    
    // 拼接结果
    for (int i = 0; i < numsSize; i++) {
        char temp[11];
        sprintf(temp, "%d", nums[i]);
        strcat(result, temp);
    }
    
    // 处理特殊情况：如果结果全是0，应该