LeetCode 剑指 Offer 45. 把数组排成最小的数

Categories:

题目描述
思路分析
1. 解法一：自定义排序（推荐）
相似题目

题目描述

✅ 剑指 Offer 45. 把数组排成最小的数

思路分析

解法一：自定义排序（推荐）

核心思路：

将所有整数转为字符串，然后对字符串数组进行自定义排序。

排序比较规则：对于两个字符串 a 和 b，若 a + b < b + a（字典序），则 a 排在 b 前面。

该比较规则的正确性：若 a + b < b + a，则将 a 放在 b 前面能使拼接结果更小。

排序完成后，将所有字符串拼接即为结果；特殊情况：若最大的数为 0（即数组全为 0），返回 "0"。

复杂度分析：

时间复杂度：O(n log n)，其中 n 为数组长度，主要开销在字符串排序。

空间复杂度：O(n)，其中 n 为数组长度，用于存储字符串数组。

import java.util.Arrays;

class Solution {
    public String minNumber(int[] nums) {
        // 将整数数组转为字符串数组
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }

        // 自定义排序：若 a+b < b+a，则 a 排在前面
        Arrays.sort(strs, (a, b) -> (a + b).compareTo(b + a));

        // 拼接所有字符串
        StringBuilder sb = new StringBuilder();
        for (String s : strs) {
            sb.append(s);
        }

        // 若最大数为 "0"，说明数组全为 0，直接返回 "0"
        return sb.charAt(0) == '0' ? "0" : sb.toString();
    }
}

import (
    "sort"
    "strconv"
    "strings"
)

func minNumber(nums []int) string {
    // 将整数数组转为字符串数组
    strs := make([]string, len(nums))
    for i, num := range nums {
        strs[i] = strconv.Itoa(num)
    }

    // 自定义排序：若 a+b < b+a，则 a 排在前面
    sort.Slice(strs, func(i, j int) bool {
        return strs[i]+strs[j] < strs[j]+strs[i]
    })

    // 拼接所有字符串
    result := strings.Join(strs, "")

    // 若最大数为 "0"，说明数组全为 0，直接返回 "0"
    if result[0] == '0' {
        return "0"
    }
    return result
}

相似题目

题目	难度	考察点
179. 最大数	中等	自定义排序 / 贪心
406. 根据身高重建队列	中等	自定义排序 / 贪心
148. 排序链表	中等	归并排序 / 链表
56. 合并区间	中等	排序 / 区间合并
452. 用最少数量的箭引爆气球	中等	排序 / 贪心
1029. 两地调度	中等	自定义排序 / 贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/45710356