数组一排开,最大的坑不是排序本身,是你以为“谁大谁放前面”就完了。
这题叫拼接最大数。给你一组非负整数,让你重新排个顺序,最后拼成一个最大的数字。乍一看像贪心,很多人上来就按数值降序排,9 > 34 > 30 > 3,结果一碰到 3 和 30 就露馅了。 这种题我第一眼不太信“数字大小”这件事,因为最后比的不是单个元素,而是拼起来谁更大。
比如:
[3, 30, 34, 5, 9]
真正要比的是:
也就是说,排序规则不是 a > b,而是看 (b + a) 和 (a + b) 谁大。谁拼出来更大,谁就应该排前面。
Java 里这题写法不复杂,关键是比较器别写歪了:
import java.util.Arrays;publicclassLargestNumber{public String largestNumber(int[] nums){ String[] arr = new String[nums.length];for (int i = 0; i < nums.length; i++) { arr[i] = String.valueOf(nums[i]); } Arrays.sort(arr, (a, b) -> (b + a).compareTo(a + b));// 全是 0 的情况要单独拦一下if ("0".equals(arr[0])) {return"0"; } StringBuilder sb = new StringBuilder();for (String s : arr) { sb.append(s); }return sb.toString(); }publicstaticvoidmain(String[] args){ LargestNumber demo = new LargestNumber(); System.out.println(demo.largestNumber(newint[]{3, 30, 34, 5, 9})); System.out.println(demo.largestNumber(newint[]{10, 2})); System.out.println(demo.largestNumber(newint[]{0, 0, 0})); }}
这里有两个地方最容易错。
一个是比较器方向。 很多人会写成 (a + b).compareTo(b + a),结果排出来是最小数,不是最大数。这种错编译不报,样例一跑就翻车。
另一个是全 0。 像 [0,0],排序拼完是 "00",但题目要的是 "0"。这种边角料不拦,提交基本过不了。
这题本质上不是数学题,也不是什么高深贪心,核心就是把“局部比较规则”找对:两个数谁在前,不看它本身大不大,只看拼接后谁更值钱。
现场做题的时候,我一般会先拿 3、30 这种最容易出错的样例试比较器。比较器一旦对了,这题后面就很顺。 难的从来不是代码那几行,难的是别被“按数字大小排序”这个直觉带偏。