Medium

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

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

解题思路

解题思路

这道题的核心是自定义排序。我们需要找到一个比较规则，使得按照这个规则排序后，拼接起来的数字最大。

关键洞察： 对于两个数字 a 和 b，我们应该比较 ab 和 ba 的大小：

  • 如果 ab > ba，则 a 应该排在 b 前面
  • 如果 ab < ba，则 b 应该排在 a 前面

例如对于 3 和 30：

  • "3" + "30" = "330"
  • "30" + "3" = "303"
  • 因为 330 > 303，所以 3 应该排在 30 前面

算法步骤：

  1. 将所有数字转换为字符串
  2. 使用自定义比较器进行排序：比较 a+b 和 b+a 的字典序
  3. 将排序后的字符串拼接
  4. 处理特殊情况：如果结果全是 0，返回 “0”

时间复杂度： O(n log n × m)，其中 n 是数组长度，m 是数字的平均长度 空间复杂度： O(n × m)，用于存储字符串

代码实现

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> strs;
        for (int num : nums) {
            strs.push_back(to_string(num));
        }
        
        sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
            return a + b > b + a;
        });
        
        if (strs[0] == "0") return "0";
        
        string result;
        for (const string& s : strs) {
            result += s;
        }
        return result;
    }
};

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        from functools import cmp_to_key
        
        strs = [str(num) for num in nums]
        
        def compare(a, b):
            if a + b > b + a:
                return -1
            elif a + b < b + a:
                return 1
            else:
                return 0
        
        strs.sort(key=cmp_to_key(compare))
        
        result = ''.join(strs)
        return '0' if result[0] == '0' else result

public class Solution {
    public string LargestNumber(int[] nums) {
        string[] strs = nums.Select(num => num.ToString()).ToArray();
        
        Array.Sort(strs, (a, b) => (b + a).CompareTo(a + b));
        
        if (strs[0] == "0") return "0";
        
        return string.Join("", strs);
    }
}

var largestNumber = function(nums) {
    const strs = nums.map(num => num.toString());
    
    strs.sort((a, b) => (b + a).localeCompare(a + b));
    
    if (strs[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log n × m)
空间复杂度O(n × m)

其中 n 是数组长度，m 是数字转换为字符串后的平均长度。排序需要 O(n log n) 次比较，每次比较需要 O(m) 时间进行字符串拼接和比较。

相关题目