示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文以 doocs/leetcode 仓库中 179. Largest Number 英文题解 与 中文题解 为骨架结合仓库内 7 种语言的Solution.*源码系统讲解给定一组非负整数重新排列每个数的顺序每个数不可拆分使之组成最大整数这一经典题目的贪心思路、比较器设计与边界处理并给出可直接运行的 Python3 / Java / C / Go / C# / TypeScript / JavaScript 七语言实现。读完本文你将掌握拼接比较法比较ab与ba决定先后这一通用排序技巧以及它在不同语言中落地为自定义比较器的完整套路。一、题目回顾把非负整数排列成最大数原题描述见 README_EN.md 与 README.md给定一组非负整数nums重新排列每个数的顺序每个数不可拆分使之组成一个最大的整数。由于结果可能非常大所以需要返回一个字符串而不是整数。示例示例 1输入nums [10,2] 输出210示例 2输入nums [3,30,34,5,9] 输出9534330约束条件约束取值数组长度1 nums.length 100元素取值范围0 nums[i] 10^9返回值字符串而非整数避免溢出题目本身很短但如何定义两个数字之间的先后关系是这道题真正的考点——它既不等于数值大小关系也不等于普通的字典序关系。二、核心难点为什么数值排序与普通字典序都不成立题解文档的思考部分README.md开门见山地指出拼接出一个最大整数。按数值或普通字典序排序都不对9应排在98前面因为998 989。下面逐一拆解这两种看似自然的思路为何失败。反例一按数值降序排列直觉上把大的数字放前面似乎合理但示例 1 已经给出了反例[10, 2]按数值降序得到[10, 2]拼接为102而把2放在10前面得到210显然更大。原因是数字的位数也会影响拼接后的整体长度与高位取值单纯比较数值大小忽略了这一点。反例二按普通字典序降序排列把数字转成字符串后按字典序降序同样不正确。题解文档给出的关键反例是9与98按字典序98 9因为比较到第 2 位时 8 与字符串 9 已结束字典序中 98 更大所以98会排在9前面但拼接结果998明显大于989即9应当排在98前面。类似的还有3与30330大于303所以3应排在30前而普通字典序会得到相反结论。示例 2 的最终答案9534330也印证了这一点——34排在3前面是因为343 334。结论需要一种拼接视角的自定义排序既然数值大小和字典序都无法直接刻画谁在前能拼出更大结果就必须针对两两拼接后的字符串大小来定义顺序。三、贪心策略以ab与ba的大小决定先后核心思想题解文档给出的解法思路非常精炼README.md比较ab与ba即可决定两串的先后整体按这个比较排序再拼接若最高位是0说明全是0返回0。也就是说对于任意两个数字字符串a与b若a b b a说明把a放在b前面能拼出更大的数因此a应排在b之前若a b b a则b应排在a之前。把这一比较规则作为排序的比较器对全部字符串排序再将结果拼接起来即可得到全局最大数。整个流程可以概括为三步转字符串将每个整数v转为字符串保留其原有的位数信息自定义排序按a b与b a的大小关系降序排列拼接与边界处理拼接所有字符串若排序后首位是0说明所有数字都是0直接返回0。为什么两两比较可以导出全局最优这是一个典型的贪心正确性论证思路若排序后的序列满足任意相邻两个字符串x、y都有x y y x则任意一对相邻元素的交换都不会让拼接结果变大而任意一个不同的排列都可以通过一系列相邻交换从当前序列变换得到因此当前序列在所有排列中拼接结果最大即为全局最优。还有一个值得注意的细节当a b b a时例如数字1与11两者拼接结果都是111谁先谁后都不影响最终答案因此比较器无需区分这种情况。边界条件全零数组必须返回0如果不做处理[0, 0]这类输入排序后拼接会得到00而正确结果应为0。由于非负整数转字符串时只有0自身会产生以0开头的字符串因此排序后只要首位字符串是0就说明数组中所有元素都是0直接返回0即可。这是各语言实现中几乎一致采用的判断方式。四、多语言实现精讲仓库源码对照仓库为该题提供了 7 种语言的独立源码文件目录 solution/0100-0199/0179.Largest Number与题解文档中的代码块一一对应。下面逐一讲解各语言如何落地上述贪心策略。Python3cmp_to_key自定义比较源码见 Solution.pyclass Solution: def largestNumber(self, nums: List[int]) - str: nums [str(v) for v in nums] nums.sort(keycmp_to_key(lambda a, b: 1 if a b b a else -1)) return 0 if nums[0] 0 else .join(nums)要点说明Python 的list.sort不支持直接传入二元比较函数需要借助functools.cmp_to_key将旧式比较函数包装为排序键本地运行需补充from functools import cmp_to_key与from typing import List比较函数语义当a b b a时返回1表示a排在b之后否则返回-1a排在b之前等价于按拼接结果降序排序完成后若nums[0] 0说明全部元素为0返回0否则直接.join(nums)拼接。JavaLambda 比较器源码见 Solution.javaclass Solution { public String largestNumber(int[] nums) { ListString vs new ArrayList(); for (int v : nums) { vs.add(v ); } vs.sort((a, b) - (b a).compareTo(a b)); if (0.equals(vs.get(0))) { return 0; } return String.join(, vs); } }要点说明通过v 把整数转为字符串存入列表比较器写成(b a).compareTo(a b)若b a大于a b返回正数a排到b之后从而保证拼接更大的组合排在前面与 Python 版语义一致String.join(, vs)完成拼接首位为0时返回0。CLambda 直接比较拼接串源码见 Solution.cppclass Solution { public: string largestNumber(vectorint nums) { vectorstring vs; for (int v : nums) vs.push_back(to_string(v)); sort(vs.begin(), vs.end(), [](string a, string b) { return a b b a; }); if (vs[0] 0) return 0; string ans; for (string v : vs) ans v; return ans; } };要点说明用to_string(v)完成整数转字符串sort的 Lambda 直接返回a b b a即拼接更大者在前作为升序排序的比较规则拼接时用ans v累积同样在vs[0] 0时提前返回。Gosort.Slice自定义比较源码见 Solution.gofunc largestNumber(nums []int) string { vs : make([]string, len(nums)) for i, v : range nums { vs[i] strconv.Itoa(v) } sort.Slice(vs, func(i, j int) bool { return vs[i]vs[j] vs[j]vs[i] }) if vs[0] 0 { return 0 } return strings.Join(vs, ) }要点说明strconv.Itoa(v)完成整数转字符串sort.Slice的 less 函数返回vs[i]vs[j] vs[j]vs[i]表示拼接更大者在前strings.Join(vs, )拼接全零时返回0。C#手写递归比较器避免拼接字符串源码见 Solution.csC# 版本实现方式与其他语言略有不同——它没有在比较器中显式拼接字符串而是手写了一个按位比较、递归处理公共前缀的IComparerstringpublic class Comparer: IComparerstring { public int Compare(string left, string right) { return Compare(left, right, 0, 0); } private int Compare(string left, string right, int lBegin, int rBegin) { var len Math.Min(left.Length - lBegin, right.Length - rBegin); for (var i 0; i len; i) { if (left[lBegin i] ! right[rBegin i]) { return left[lBegin i] right[rBegin i] ? -1 : 1; } } if (left.Length - lBegin right.Length - rBegin) { return 0; } if (left.Length - lBegin right.Length - rBegin) { return Compare(left, right, lBegin len, rBegin); } else { return Compare(left, right, lBegin, rBegin len); } } } public class Solution { public string LargestNumber(int[] nums) { var sb new StringBuilder(); var strs nums.Select(n n.ToString(CultureInfo.InvariantCulture)).OrderByDescending(s s, new Comparer()); var nonZeroOccurred false; foreach (var str in strs) { if (!nonZeroOccurred str 0) continue; sb.Append(str); nonZeroOccurred true; } return sb.Length 0 ? 0 : sb.ToString(); } }要点说明比较器先逐位比较两串的公共前缀若前缀相同则把较长串的剩余部分与较短串继续递归比较逻辑上与比较a b、b a等价但避免了创建拼接字符串主逻辑通过OrderByDescending按该比较器降序排列边界处理采用了另一种等价写法拼接时跳过前导0若最终StringBuilder为空则返回0同样能正确处理[0, 0]这类全零输入。TypeScript数值化比较源码见 Solution.tsfunction largestNumber(nums: number[]): string { nums.sort((a, b) { const [ab, ba] [String(a) String(b), String(b) String(a)]; return ba - ab; }); return nums[0] ? nums.join() : 0; }要点说明比较器将a b与b a两个拼接字符串通过一元转为数值后相减ba - ab 0表示ba ab即b应排在a前全零判断改用nums[0] ? ... : 0排序后首位为0数值意义上的0即返回0需要注意nums[i]最大可达10^9两个拼接串最长约 20 位已超出 JavaScriptNumber的安全整数范围Number.MAX_SAFE_INTEGER约 9.007e15数值化比较在高位场景下存在潜在的精度风险在题目给定的数据范围内该实现可正确通过但这也是部分语言选择纯字符串比较的原因之一。JavaScript与 TypeScript 相同的思路源码见 Solution.js实现与 TypeScript 版完全一致只是省略了类型标注function largestNumber(nums) { nums.sort((a, b) { const [ab, ba] [String(a) String(b), String(b) String(a)]; return ba - ab; }); return nums[0] ? nums.join() : 0; }五、复杂度分析在约束1 nums.length 100、0 nums[i] 10^9的前提下从上述实现可以推断时间开销排序为算法主体。比较次数为O(n log n)每次比较涉及长度不超过约 10 位的两个字符串拼接a b、b a合并长度不超过约 20 位可视为常数级因此整体时间复杂度为O(n log n)对于n 100的规模非常轻松空间开销需要存放转换后的字符串数组空间复杂度为O(n)部分语言实现中排序器与拼接过程还会产生少量临时字符串。六、小结与仓库资源导航本题的核心套路可以浓缩为三点不要比较数值或字典序而要比较a b与b a两个拼接结果用自定义比较器完成降序排序各语言实现方式各异cmp_to_key、Lambda、sort.Slice、手写IComparer等但语义完全一致全零输入返回0避免出现00这类前导零结果。如果你希望进一步研究该题在仓库中的完整形态可以参考以下文件中文题解README.md英文题解README_EN.md各语言实现与题解文档代码块一一对应Solution.pySolution.javaSolution.cppSolution.goSolution.csSolution.tsSolution.js拼接比较法a b与b a定序不仅是这道题的答案也是面试中处理数字拼接取极值类问题如排序数组排成最小数等变体的通用思维模型值得熟练掌握。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode 179. 最大数Largest Number题解基于 ab 与 ba 比较的自定义排序法LeetCode 179. 最大数Largest Number题解基于 ab 与 ba 比较的自定义排序法 本篇技术指南围绕 LeetCode 第 1示例工程LeetCode-Go 题解 179. Largest Number拼接比较排序法求解最大数LeetCode Go 题解 179. Largest Number拼接比较排序法求解最大数 本篇以 LeetCode Go 仓库中 179. Largest示例工程LeetCode 179 Largest Number 题解字符串拼接比较器与排序算法在 leetcode1/leetcode 仓库中的多语言实现LeetCode 179 Largest Number 题解字符串拼接比较器与排序算法在 leetcode1/leetcode 仓库中的多语言实现 本篇技术指示例工程上一篇dhtcrawler2 vs dhtcrawler为什么选择这个革命性的P2P爬虫升级版下一篇GetQzonehistory 完整指南如何把QQ空间说说历史备份到本地创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考