题目描述
思路解析动画文字版
记住这条比较规则:a 在 b 前 ⇔ 拼接 a+b 比 b+a 大。下面用冒泡排序一对一对地套用它。
初始数组就是题目给的顺序,还没排。我们用冒泡排序,从左到右一对一对比较相邻两个数。
比较相邻的 3 和 30:拼成 "330" 和 "303",前者大,3 该排在前,不动。
比较相邻的 30 和 34:拼成 "3034" 和 "3430",后者大,说明 34 该排在前,要交换。
因为 "3430" 比 "3034" 大,把 34 和 30 交换位置:现在下标 1 是 34、下标 2 是 30。
比较相邻的 30 和 5:拼成 "305" 和 "530",后者大,说明 5 该排在前,要交换。
因为 "530" 比 "305" 大,把 5 和 30 交换位置:现在下标 2 是 5、下标 3 是 30。
比较相邻的 30 和 9:拼成 "309" 和 "930",后者大,说明 9 该排在前,要交换。
因为 "930" 比 "309" 大,把 9 和 30 交换位置:现在下标 3 是 9、下标 4 是 30。
这一趟走完,最该排在末尾的数已经沉到右边(标蓝的就是已确定位置的)。下一趟只需处理左边没排好的部分。
比较相邻的 3 和 34:拼成 "334" 和 "343",后者大,说明 34 该排在前,要交换。
因为 "343" 比 "334" 大,把 34 和 3 交换位置:现在下标 0 是 34、下标 1 是 3。
比较相邻的 3 和 5:拼成 "35" 和 "53",后者大,说明 5 该排在前,要交换。
因为 "53" 比 "35" 大,把 5 和 3 交换位置:现在下标 1 是 5、下标 2 是 3。
比较相邻的 3 和 9:拼成 "39" 和 "93",后者大,说明 9 该排在前,要交换。
因为 "93" 比 "39" 大,把 9 和 3 交换位置:现在下标 2 是 9、下标 3 是 3。
这一趟走完,最该排在末尾的数已经沉到右边(标蓝的就是已确定位置的)。下一趟只需处理左边没排好的部分。
比较相邻的 34 和 5:拼成 "345" 和 "534",后者大,说明 5 该排在前,要交换。
因为 "534" 比 "345" 大,把 5 和 34 交换位置:现在下标 0 是 5、下标 1 是 34。
比较相邻的 34 和 9:拼成 "349" 和 "934",后者大,说明 9 该排在前,要交换。
因为 "934" 比 "349" 大,把 9 和 34 交换位置:现在下标 1 是 9、下标 2 是 34。
这一趟走完,最该排在末尾的数已经沉到右边(标蓝的就是已确定位置的)。下一趟只需处理左边没排好的部分。
比较相邻的 5 和 9:拼成 "59" 和 "95",后者大,说明 9 该排在前,要交换。
因为 "95" 比 "59" 大,把 9 和 5 交换位置:现在下标 0 是 9、下标 1 是 5。
这一趟走完,最该排在末尾的数已经沉到右边(标蓝的就是已确定位置的)。下一趟只需处理左边没排好的部分。
所有相邻对都比较过、不再交换,排序结束。整组数已按「拼接更大者在前」排好。
把排好的数从左到右首尾拼起来,就得到最大数 9534330。(若首位是 0,说明全是 0,直接返回 "0"。)
三个高频追问:规则为何正确、全 0 边界、以及为什么必须转字符串。
参考代码
from functools import cmp_to_keydef largestNumber(nums): arr = list(map(str, nums)) # a 排 b 前 ⇔ a+b 比 b+a 大 → 返回 -1 def cmp(a, b): if a + b > b + a: return -1 if a + b < b + a: return 1 return 0 arr.sort(key=cmp_to_key(cmp)) res = ''.join(arr) return '0' if res[0] == '0' else res # 防全 0复杂度
- 时间:O(n log n · k),排序 O(n log n) 次比较,每次比较是长度约 k 的字符串拼接与比较
- 空间:O(n · k),把每个数转成字符串存下来,k 为单个数字的位数
易错点
面试追问把动画讲成自己的话
追问为什么这个比较规则能保证全局最大?
追问输入里有 0 要注意什么?
追问为什么要先转成字符串?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
H 指数
LeetCode 274 · 中等 · 沿着 排序套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题