【LeetCode】179 把数组排成最大的数

优质

小牛编辑

126浏览

2023-12-01

这道题是 LeetCode 179 题：给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。《剑指 Offer》的 45 题也是同样的题目，只不过要求排列成最小的数。

题解

这两道题都要求我们将数组中的元素按照某种排序规则升序排序。如果要得到最小的数，那就将排序后的数组从前往后拼接；如果要得到最大的数，那就将排序后的数组从后往前拼接。因此，本文仅以《剑指 Offer》的 45 题为例，分析如何对数组进行排序，才能排列成最小的数。至于 LeetCode 179 题，只需修改数组的遍历顺序。

简单地思考一下，既然目标是排列成最小的数，那么肯定是按照字符串大小升序排序，这样才能保证拼接出来的数字高位更小。比如 35 和 324，按照字符串大小排序，324 排在 35 前面，而 32435 < 35324，显然符合要求。

但是有一个特殊情况：一个数是另一个数的子串。在这种情况下，按照字符串大小排序不一定能得到正确的结果。比如 23 和 231，如果按照字符串大小排序，那么 23 排在 231 前面，但是却有 23231 > 23123，也就是说，这种顺序得到的并不是最小的数。

我们这样来分析：设两个数字的字符串表示分别为 A 和 AB，前一个数是后一个数的子串，这两个数拼出的数字为 AAB 与 ABA。显然，如果 AAB < ABA，即 B < A，那么 A 应该排在 AB 的前面；反之，如果 ABA < AAB，即 A < B，那么 AB 应该排在 A 的前面。

因此我们可以总结出符合本题要求的排序规则。设两个数字的字符串表示分别为 $s_1$ 和 $s_2$：

如果 $s_1$、$s_2$ 互相都不是对方的子串，那么直接比较两者的字符串顺序
如果 $s_1$ 是 $s_2$ 的子串，那么比较 $s_1$ 与 $s_2-s_1$ 的字符串顺序。$s_2-s_1$ 表示 $s_2$ 中去掉 $s_1$ 后剩余的串
如果 $s_2$ 是 $s_1$ 的子串，只需将上一步的比较顺序交换一下即可

举例：

35 和 324：按照字符串大小排序，324 < 35
23 和 231：前者是后者的子串，因此需要比较 23 与 1。23 > 1，所以有 23 > 231，即 23 排在 231 的后面
23 和 234：前者是后者的子串，因此需要比较 23 与 4。23 < 4，所以有 23 < 234，即 23 排在 234 的前面

比较函数的实现：

// 比较两个数字 a < b
func Compare(a, b string) bool { 
	p, q := 0, 0
	for p < len(a) && q < len(b) { // 按照字符序比较大小
		if a[p] < b[q] {
			return true
		}
		if a[p] > b[q] {
			return false
		}
		p++
		q++
	}
	if len(a) == len(b) { // a == b
		return true
	}
	if len(a) < len(b) { // a 是 b 的子串
		return Compare(a, b[q:])
	}
	return Compare(a[p:], b) // b 是 a 的子串
}

《剑指 offer》面试题 45 完整代码：

func minNumber(nums []int) string {
	list := SortableList(nums)
	sort.Sort(list)
	res := ""
	for i := 0; i < len(list); i++ {
		res += strconv.Itoa(list[i])
	}
	return res
}

type SortableList []int

func (this SortableList) Len() int {
	return len(this)
}

func (this SortableList) Swap(i, j int) {
	this[i], this[j] = this[j], this[i]
}

func (this SortableList) Less(i, j int) bool {
	a, b := strconv.Itoa(this[i]), strconv.Itoa(this[j])
	return Compare(a, b)
}

func Compare(a, b string) bool {
	p, q := 0, 0
	for p < len(a) && q < len(b) { // 按照字符序比较大小
		if a[p] < b[q] {
			return true
		}
		if a[p] > b[q] {
			return false
		}
		p++
		q++
	}
	if len(a) == len(b) { // a == b
		return true
	}
	if len(a) < len(b) { // a 是 b 的子串
		return Compare(a, b[q:])
	}
	return Compare(a[p:], b) // b 是 a 的子串
}

LeetCode 179 题只需要反向遍历列表，同时处理一下数字全为 0 的特殊情况：

func largestNumber(nums []int) string {
	list := SortableList(nums)
	sort.Sort(list)
	if list[len(list)-1] == 0 { // nums 全是 0
		return "0"
	}
	res := ""
	for i := len(list)-1; i >= 0; i-- {
		res += strconv.Itoa(list[i])
	}
	return res
}

总结

这道题还有一个更简单的解法是：设两个数字的字符串表示分别为 A 和 B，这两个数拼出的数字为 AB 与 BA。如果 AB < BA，那么 A 应该排在 B 的前面。比较函数可以写为：

func Compare(a, b string) bool {
	return a+b < b+a
}

但是在这篇题解中，我们忽略了最重要的一部分：证明比较规则的有效性。我们只是定义了两个数的比较规则，却将它用来排序含有多个数字的数组，那么排序后的数组中，任两个数都符合我们定义的这个比较规则吗？或许这是很“显然”的事，但是我们应该给出严格的数学证明。

一个集合上的二元关系需要满足 3 个条件：自反性、对称性和传递性（等价关系 - 维基百科）。如果我们上面定义的比较规则满足这三个特性，那么它就是有效的。关于这三个特性的证明，可以查看《剑指 offer》的对应章节，或者 LeetCode 的这篇回答，此处不再赘述。