最大数 - Python/C语言实现详解

题目描述

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意： 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

输入：nums = [10,2]
输出："210"

示例 2：

输入：nums = [3,30,34,5,9]
输出："9534330"

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 10⁹

解题思路

核心思想

问题的关键在于如何定义数字的"大小"。对于两个数字 x 和 y，我们不应该直接比较它们的数值大小，而是比较两种拼接方式：

• x 在前 y 在后：xy
• y 在前 x 在后：yx

如果 xy > yx，那么 x 应该排在 y 前面，这样才能得到更大的拼接结果。

C语言实现

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

// 比较函数
int compare(const void *a, const void *b) {
    char s1[24], s2[24];
    sprintf(s1, "%d%d", *(int*)a, *(int*)b);
    sprintf(s2, "%d%d", *(int*)b, *(int*)a);
    return strcmp(s2, s1);
}

char* largestNumber(int* nums, int numsSize) {
    // 排序
    qsort(nums, numsSize, sizeof(int), compare);
    
    // 处理全零情况
    if (nums[0] == 0) {
        char* result = malloc(2);
        strcpy(result, "0");
        return result;
    }
    
    // 计算总长度
    int len = 0;
    for (int i = 0; i < numsSize; i++) {
        int n = nums[i];
        do { len++; n /= 10; } while (n);
    }
    
    // 拼接结果
    char* result = malloc(len + 1);
    char* p = result;
    for (int i = 0; i < numsSize; i++) {
        p += sprintf(p, "%d", nums[i]);
    }
    return result;
}

Python实现

class Solution:
    def largestNumber(self, nums):
        nums = list(map(str, nums))
        nums.sort(key=lambda x: x * 10, reverse=True)
        return '0' if nums[0] == '0' else ''.join(nums)

核心优化点

1. 比较函数简化：直接使用 sprintf 拼接，避免多次字符串操作
2. 内存优化：精确计算所需内存，避免浪费
3. 逻辑简化：减少不必要的条件判断
4. Python技巧：利用字符串乘法实现高效比较

测试用例

int main() {
    int nums1[] = {10, 2};
    char* res1 = largestNumber(nums1, 2);
    printf("输出: %s\n", res1);  // "210"
    free(res1);
    
    int nums2[] = {3, 30, 34, 5, 9};
    char* res2 = largestNumber(nums2, 5);
    printf("输出: %s\n", res2);  // "9534330"
    free(res2);
    
    return 0;
}