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

题解

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

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

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

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

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

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

举例:

  • 35324:按照字符串大小排序,324 < 35
  • 23231:前者是后者的子串,因此需要比较 23123 > 1,所以有 23 > 231,即 23 排在 231后面
  • 23234:前者是后者的子串,因此需要比较 23423 < 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
}

总结

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

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

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

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

本文发表在我的博客 https://imageslr.com/。我也会分享更多的题解,一起交流,共同进步!