企业官网建设流程全解析

LeetCode 179 Largest Number 的 Go 题解：自定义比较器快排与 a+b、b+a 拼接比较

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇以 LeetCode-Go 仓库中 179. Largest Number 题解文档 为核心，完整讲解"给定一组非负整数，重排它们使得拼接出的数字最大"这一题的解题思路：为什么朴素字符串比较会失效、如何用a+b与b+a的拼接比较构造自定义排序规则，并结合 仓库源码 逐行剖析快速排序的分区实现与前导零处理细节，最后给出仓库自带的完整测试用例与运行方式。读完后你可以独立复现这道题的 Go 实现，并理解自定义比较器在排序类问题中的通用套路。

一、题目与示例

原题描述（摘自 README.md）：给定一个非负整数列表，将它们排列组合成一个最大的数字。

示例 1：

Input: [10,2] Output: "210"

示例 2：

Input: [3,30,34,5,9] Output: "9534330"

注意：结果可能非常大，因此需要返回字符串而不是整数（The result may be very large, so you need to return a string instead of an integer.）。

这道题的题面非常短，但陷阱很典型：排序的规则并不是"数值大的在前"，也不是"字符串字典序大的在前"，而是要设计一个面向最终拼接结果的比较规则。

二、核心思路：为什么不能直接用字符串大小比较

很容易想到第一步：把数字都转成字符串，利用字符串比较来排序，这样 9 开头的一定排在最前面。但原文明确指出这样做有一个错误——"3" 和 "30" 的比较：按字典序，"30" 比 "3" 大（因为第 2 个字符 '0' 与 '3' 比较后 "30" 更长、前缀相同），于是排序会把 "30" 放在 "3" 前面，拼出 "303"；而实际上 "3" 应该排在 "30" 前面，拼出 "330" 才是更大的数。

原文给出的修正方法是：在比较两个字符串大小时，不单纯只用字符串顺序进行比较，而是加入一个"互相拼接"的维度：

aStr := a + b bStr := b + a

通过比较aStr和bStr的大小来得出是 a 大还是 b 大。还是 "3" 和 "30" 的例子：

aStr := "3" + "30" = "330" bStr := "30" + "3" = "303"

"330" > "303"，所以 "3" 应排在 "30" 前面。通过互相补齐位数后再比较，前缀型数字（一个是另一个的前缀，如 12 与 128、12 与 121）就不会再被字典序误判。

从源码结构看，这个比较器正是整个解法的关键：排序部分没有任何额外的数值转换，正确性完全由"谁拼在前面更大"这一局部规则保证。

三、源码逐段解析

完整实现位于 179. Largest Number.go，共 4 个函数：largestNumber、toStringArray、partitionString、quickSortString。

3.1 主函数：空数组、转字符串、拼接与去零

func largestNumber(nums []int) string { if len(nums) == 0 { return "" } numStrs := toStringArray(nums) quickSortString(numStrs, 0, len(numStrs)-1) res := "" for _, str := range numStrs { if res == "0" && str == "0" { continue } res = res + str } return res }

几个要点：

• 空输入返回空串：len(nums) == 0时直接返回""，对应测试用例[]int{}→""；
• 排序后拼接：调用quickSortString对字符串数组原地降序排序，再顺序拼成结果；
• 前导零处理：如果数组全是 0（如[0, 0]），排序后拼出来会是"00"，语义上应返回"0"。这里的写法是：一旦res已经等于"0"，后续遇到的"0"一律跳过，最终把"00"收敛为"0"。这个条件res == "0" && str == "0"的写法比较精巧——只有当结果当前恰好只剩一个 "0" 时才去重，不影响"10"这类含零的正常结果。

3.2 数字转字符串

func toStringArray(nums []int) []string { strs := make([]string, 0) for _, num := range nums { strs = append(strs, strconv.Itoa(num)) } return strs }

就是标准的strconv.Itoa批量转换，为后面按字符串做比较做准备。

3.3 关键：自定义比较器的快排分区

func partitionString(a []string, lo, hi int) int { pivot := a[hi] i := lo - 1 for j := lo; j < hi; j++ { ajStr := a[j] + pivot pivotStr := pivot + a[j] if ajStr > pivotStr { // 这里的判断条件是关键 i++ a[j], a[i] = a[i], a[j] } } a[i+1], a[hi] = a[hi], a[i+1] return i + 1 }

这是标准 Lomuto 方案的快速排序分区，唯一不同之处在判断条件：

• 取a[hi]作为基准pivot；
• 对每个a[j]，不直接比较a[j]与pivot，而是比较a[j] + pivot与pivot + a[j]这两个拼接串——即"把 a[j] 放在 pivot 前面"和"把 pivot 放在 a[j] 前面"哪个拼出来更大；
• 若前者更大，则a[j]属于"应排在 pivot 之前"的分区，执行i++并交换。

源码注释也直接标注了这一点：// 这里的判断条件是关键。

3.4 递归排序入口

func quickSortString(a []string, lo, hi int) { if lo >= hi { return } p := partitionString(a, lo, hi) quickSortString(a, lo, p-1) quickSortString(a, p+1, hi) }

quickSortString(numStrs, 0, len(numStrs)-1)从整个区间开始递归。从源码结构看，这里的快排选取最后一个元素作为 pivot 且没有随机化，属于最直接的教科书实现；在 LeetCode 本题的数据规模下没有问题，但要意识到这是未经优化的快排形态。排序完成后再回到largestNumber主函数做拼接，整个流程就是：转字符串 → 自定义比较器快排 → 拼接去零。

四、为什么这个比较规则对整道题成立

a+b > b+a定义的是"谁应该排在谁前面"。原理解释是：拼接出的最终数字，其大小由每一位决定；比较两个相邻元素的先后顺序时，只要保证"任意相邻一对都满足更优的相对顺序"，整体拼接结果就是最大的。而a+b与b+a的比较恰好就是针对"相邻拼接"的最优判定——它把"两者谁靠前"这一局部决策问题，转化成了两个等长字符串的字典序比较，天然绕开了字符串长短不一时字典序失效的问题（这正是 "30" 与 "3" 这类前缀陷阱的根源）。

仓库测试用例 179. Largest Number_test.go 中的多组数据也印证了这一点，尤其是两组典型的前缀型用例：

[12, 121]这组尤其值得注意：按字典序 "121" > "12"，恰好结论也对，但理由不同——真正生效的是拼接比较 "12112" > "12121"。可以推断，这类用例正是为了排除"恰好靠字典序蒙对"的实现而设计的。

五、如何运行与验证

仓库根目录的 go.mod 声明了 Go 1.19 模块环境。本题目录下的测试文件采用"打印输入输出对照"的方式组织：Test_Problem179遍历全部用例并调用largestNumber打印实际结果，与上方表格中的期望值逐一比对即可人工核验。

在仓库根目录运行本题的测试：

go test -v ./leetcode/0179.Largest-Number/

也可以运行仓库自带的 gotest.sh 对全部题解做带覆盖率的回归：

bash gotest.sh

该脚本执行go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...，一次性产出单一合法的覆盖率文件（脚本注释中说明了这是为避免多包分次生成 profile 导致的格式问题）。

六、小结

回到 题解文档 的原始脉络，本仓库 179 题的完整解法可以浓缩为三步：

1. 转字符串：用strconv.Itoa把[]int映射为[]string，为自定义比较做准备；
2. 自定义比较器排序：以a+b与b+a的字典序判定两元素先后，配合 Lomuto 分区快排原地降序排序；
3. 拼接与去零：顺序拼接结果，用res == "0" && str == "0"的条件把全零输入收敛为"0"。

这一"拼接比较器"的模式不局限于本题，凡是"重排元素使拼接结果最优"的题型（如按特定顺序最大化/最小化拼接串），都可以复用同样的比较器设计思路；而 源码实现 与 测试用例 中的前缀型数据（12/128、12/121）则是检验比较器正确性的最佳判例。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go