解题思路

• 核心思想：把每个数字转成字符串，通过自定义排序决定谁应排在谁前面。对于任意两个字符串 a、b，若拼接 a+b 大于 b+a（按字典序比较），则应让 a 排在 b 前面。这是一种贪心 + 自定义比较器的经典做法，能保证全局最优。

• 关键细节：排序完成后将所有字符串依次拼接。如果最高位是 '0'，说明所有数都是零，直接返回 "0"。

• 实现步骤：

  1. 读入 n 和后续 n 个非负整数；
  2. 将数字转为字符串数组；
  3. 按比较规则对字符串数组排序（比较 x+y 与 y+x）；
  4. 处理全零特判并拼接输出。

复杂度分析

• 设有 n 个数，每个数的字符串长度平均为 k：

  • 时间复杂度：排序需要 O(n log n) 次比较，每次比较拼接并比较两个长度不超过 k 的字符串，代价 O(k)，总体为 O(n log n * k)。
  • 空间复杂度：存放字符串与排序辅助空间约为 O(n * k)。

代码实现

Python

# 功能函数：将列表中的非负整数重排，拼接成最大数
from functools import cmp_to_key

def largest_number(nums):
    # 自定义比较：若x+y > y+x，则x应在前
    def cmp(a, b):
        if a + b > b + a:
            return -1
        elif a + b < b + a:
            return 1
        else:
            return 0

    # 将数字转换为字符串，便于拼接比较
    strs = [str(x) for x in nums]
    # 排序
    strs.sort(key=cmp_to_key(cmp))
    # 特判：若最大位为'0'，则全部为0
    if strs[0] == '0':
        return '0'
    # 拼接结果
    return ''.join(strs)

if __name__ == "__main__":
    # 读入数据（ACM风格）
    import sys
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    # 后续 n 个数
    nums = list(map(int, data[1:1+n]))
    ans = largest_number(nums)
    print(ans)

Java

// 功能函数放在类中但在 main 之外；ACM风格读取输入并输出结果
import java.util.*;

public class Main {
    // 将数组重排并拼接成最大数
    public static String largestNumber(List<String> nums) {
        // 自定义比较器：按 (a+b) 与 (b+a) 的字典序比较，降序排列
        Collections.sort(nums, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                String ab = a + b;
                String ba = b + a;
                return ba.compareTo(ab); // ba大则b在前，实现降序
            }
        });
        // 若首元素为"0"，说明所有数字都是0
        if (nums.size() > 0 && nums.get(0).equals("0")) {
            return "0";
        }
        // 拼接结果
        StringBuilder sb = new StringBuilder();
        for (String s : nums) sb.append(s);
        return sb.toString();
    }

    public static void main(String[] args) {
        // 默认不用快读；若数据很大可改用BufferedReader
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<String> arr = new ArrayList<>();
        // 读取第二行的 n 个数字（以字符串读入，避免大数问题）
        for (int i = 0; i < n; i++) {
            arr.add(sc.next());
        }
        sc.close();
        String ans = largestNumber(arr);
        System.out.println(ans);
    }
}

C++

// 功能函数在主函数外；ACM风格输入输出
#include <bits/stdc++.h>
using namespace std;

// 将非负整数字符串重排，拼成最大数
string largestNumber(vector<string>& nums) {
    // 自定义比较器：若 a+b > b+a，则 a 应在前
    sort(nums.begin(), nums.end(), [](const string& a, const string& b) {
        return a + b > b + a;
    });
    // 全零特判
    if (!nums.empty() && nums[0] == "0") return "0";
    // 拼接结果
    string res;
    res.reserve(nums.size() * 10); // 预留一定空间，减少拼接开销
    for (const auto& s : nums) res += s;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<string> nums;
    nums.reserve(n);
    // 读取 n 个数为字符串，避免大数溢出
    for (int i = 0; i < n; ++i) {
        string x;
        cin >> x;
        nums.push_back(x);
    }

    string ans = largestNumber(nums);
    cout << ans << "\n";
    return 0;
}

题目内容

给定一个正整数及非负整数 $nums$ 的列表，第一个正整数表示 $nums$ 列表中数字的总个数，需要将 $nums$ 列表中数据排列组合出一个最大的数并返回它。

输入描述

输入两行数字，第一行仅有一个数字，代表待组合数据的总个数，第二行是待组合的数字的集合，数据之间使用空格间隔。

输出描述

输出能组成最大的值

样例1

输入

3
1 3 2

输出

321