为什么根据「拼接结果的字典序大小」决定「其在序列里的相对关系」是正确的

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

这是 LeetCode 上的 179. 最大数 ，难度为中等。

Tag : 「贪心」

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

输入：nums = [10,2]

输出："210"
复制代码

示例 2：

输入：nums = [3,30,34,5,9]

输出："9534330"
复制代码

示例 3：

输入：nums = [1]

输出："1"
复制代码

示例 4：

输入：nums = [10]

输出："10"
复制代码

提示：

1 <= nums.length <= 100
0 <= nums[i] <= $109$

贪心解法

对于 $nums$ 中的任意两个值 $a$ 和 $b$ ，我们无法直接从常规角度上确定其大小/先后关系。

但我们可以根据「结果」来决定 $a$ 和 $b$ 的排序关系：

如果拼接结果 $ab$ 要比 $ba$ 好，那么我们会认为 $a$ 应该放在 $b$ 前面。

另外，注意我们需要处理前导零（最多保留一位）。

代码：

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] ss = new String[n];
        for (int i = 0; i < n; i++) ss[i] = "" + nums[i];
        Arrays.sort(ss, (a, b) -> {
            String sa = a + b, sb = b + a ;
            return sb.compareTo(sa);
        });
        
        StringBuilder sb = new StringBuilder();
        for (String s : ss) sb.append(s);
        int len = sb.length();
        int k = 0;
        while (k < len - 1 && sb.charAt(k) == '0') k++;
        return sb.substring(k);
    }
}
复制代码

时间复杂度：由于是对 $String$ 进行排序，当排序对象不是 $Java$ 中的基本数据类型时，不会使用快排（考虑排序稳定性问题）。Arrays.sort() 的底层实现会「元素数量/元素是否大致有序」决定是使用插入排序还是归并排序。这里直接假定使用的是「插入排序」。复杂度为 $O(n^2)$
空间复杂度： $O(n)$

证明

上述解法，我们需要证明两个内容：

该贪心策略能取到全局最优解。
这样的「排序比较逻辑」应用在集合 $nums$ 上具有「全序关系」。

1. 该贪心策略能取到全局最优解

令我们经过这样的贪心操作得到的贪心解为 $ans$ ，真实最优解为 $max$ 。

由于真实最优解为全局最大值，而我们的贪心解至少是一个合法解（一个数），因此天然有 $ans \leqslant max$ 。

接下来我们只需要证明 $ans \geqslant max$ ，即可得 $ans = max$ （贪心解即为最优解）。

我们使用「反证法」来证明 $ans \geqslant max$ 成立：

假设 $ans \geqslant max$ 不成立，即有 $ans < max$ 。

$ans$ 和 $max$ 都是由同样一批数字凑成的，如果有 $ans < max$ 。

这意味着我们可以将 $ans$ 中的某些低位数字和高位数字互换，使得 $ans$ 更大（调整为 $max$ ），这与我们根据「结果」进行排序的逻辑冲突。

因此 $ans < max$ 必然不成立，得证 $ans \geqslant max$ 成立，结合 $ans \leqslant max$ 可得贪心解为最优。

举个?，如果有 $ans < max$ ，那么意味着在 $ans$ 中至少有一对数字互换可以使得 $ans$ 变大，

那么在排序逻辑中 $x$ 所在的整体（可能不只有 $x$ 一个数）应该被排在 $y$ 所在的整体（可能不只有 $y$ 一个数）前面。

2. 全序关系

我们使用符号 $@$ 来代指我们的「排序」逻辑：

如果 $a$ 必须排在 $b$ 的前面，我们记作 $a @ b$ ；
如果 $a$ 必须排在 $b$ 的后面，我们记作 $b @ a$ ；
如果 $a$ 既可以排在 $b$ 的前面，也可以排在 $b$ 的后面，我们记作 $a\#b$ ；

2.1 完全性

具有完全性是指从集合 $nums$ 中任意取出两个元素 $a$ 和 $b$ ，必然满足 $a @ b$ 、 $b @ a$ 和 $a\#b$ 三者之一。

这点其实不需要额外证明，因为由 $a$ 和 $b$ 拼接的字符串 $ab$ 和 $ba$ 所在「字典序大小关系中」要么完全相等，要么具有明确的字典序大小关系，导致 $a$ 必须排在前面或者后面。

2.2 反对称性

具有反对称性是指由 $a@b$ 和 $b@a$ 能够推导出 $a\#b$ 。

$a@b$ 说明字符串 $ab$ 的字典序大小数值要比字符串 $ba$ 字典序大小数值大。

$b@a$ 说明字符串 $ab$ 的字典序大小数值要比字符串 $ba$ 字典序大小数值小。

这样，基于「字典序本身满足全序关系」和「数学上的 $a \geqslant b$ 和 $a \leqslant b$ 可推导出 $a = b$ 」。

得证 $a@b$ 和 $b@a$ 能够推导出 $a\#b$ 。

2.3 传递性

具有传递性是指由 $a@b$ 和 $b@c$ 能够推导出 $a@c$ 。

这里的「传递性」其实也可以使用与官方题解类似的手法来证明。

我们可以利用「两个等长的拼接字符串，字典序大小关系与数值大小关系一致」这一性质来证明，因为字符串 $ac$ 和 $ca$ 必然是等长的。

接下来，让我们从「自定义排序逻辑」出发，换个思路来证明 $a@c$ ：

然后我们只需要证明在不同的 $i$ $j$ 关系之间（共三种情况）， $a@c$ 恒成立即可：

当 $i == j$ 的时候：

当 $i > j$ 的时候：

当 $i < j$ 的时候：

综上，我们证明了无论在何种情况下，只要有 $a@b$ 和 $b@c$ 的话，那么 $a@c$ 恒成立。

我们之所以能这样证明「传递性」，本质是利用了自定义排序逻辑中「对于确定任意元素 $a$ 和 $b$ 之间的排序关系只依赖于 $a$ 和 $b$ 的第一个不同元素之间的大小关系」这一性质。

找 $i$ 的越界问题

考虑

(1) a = 304 b = 30
(2) a = 301 b = 30

两种情况。

显然，（1）下我们会得到 $a@b$ ，而（2）下我们会得到 $b@a$

但是，在这种情况下 $i$ 实际上位于 $b$ 界外，那我们还能不能找 $i$ 呢？ $b[i]$ 是多少呢？

实际上是可以的，我们在比较 $a$ 和 $b$ 的时候，实际上是在比较 $ab$ 和 $ba$ 两个字符串，所以实际上我们是在用 $a[0]$ , $a[1]$ , $a[2]$ … 去填补 $b$ 本体结束后的空缺。换而言之（1）和（2）里的 b 实际上被填补为 303 （填进来 $a[0]$ ）