为什么根据「拼接结果的字典序大小」决定「其在序列里的相对关系」是正确的｜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] <= 109109

贪心解法

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

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

如果拼接结果 abab 要比 baba 好，那么我们会认为 aa 应该放在 bb 前面。

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

代码：

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);
    }
}
复制代码

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

证明

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

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

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

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

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

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

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

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

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

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

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

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

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

2. 全序关系

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

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

2.1 完全性

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

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

2.2 反对称性

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

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

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

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

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

2.3 传递性

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

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

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

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

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

1. 当 i == ji==j 的时候：

2. 当 i > ji>j 的时候：

3. 当 i < ji<j 的时候：

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

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

找 ii 的越界问题

考虑

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

两种情况。

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

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

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

再比如

（3）a = 3131248 b = 3131 ，比较的时候实际上是用 aa 开头的 4 位去填补上 bb 的空缺，所以 bb 实际上相当于 31313131

最后

这是我们「刷穿 LeetCode」系列文章的第 No.179 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。