华为面试题，我的回忆杀

写在前面

今天节日，为了上来和大家道一声冬至快乐，专门加更一篇。

正当我愁写哪个公司的原题时，发现「华为」题单中的 top5 有一道十分眼熟的题。

我依稀记得，当时我已经坚持日更 LeetCode 每日一题大概

多天？

但常看的留言读者还是只有那么几位。

直到这一题成为了每日一题。

也许是题解的严谨性碰巧做到了独一档，所以收获了大家的认可。

点赞和留言达到了新高，同时也被官方标为精选：

从那以后，熟悉的面孔越来越多，跟随刷穿 LeetCode 的大队也越发壮大。

按道理，这样的时刻，这样的题目，我应该记得很清楚才对，但事实没有。

人就是这样的，在信息过载年代，能被记住的东西可能也只是暂时。

包括现在，我连当时连续日更的具体天数，这个记录都忘了。

只记得好像是一个

字头的三位数？两年多？真的忘记了。

但，陪大家每天快乐刷题的感觉不会忘。

我想过去几年，做过最正确的决定。

就是做了这个公众号和一些社群。

让我们在任意时刻找到彼此。

哪怕我没有登陆 LeetCode，你还是可以在后台留言找到我，我也还是可以发推文来联系大家。

不失联，就一切都好。

冬至快乐鸭，我重要的各位读者大人 🥟

题目描述

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

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

示例 1：

输入：nums = [10,2]

输出："210"

示例 2：

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

输出："9534330"

提示：

贪心

对于

中的任意两个值

和

，我们无法直接从常规角度上确定其大小/先后关系。

但我们可以根据「结果」来决定

和

的排序关系：

如果拼接结果

要比

好，那么我们会认为

应该放在

前面。

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

Java 代码：

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);
    }
}

C++ 代码：

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        int n = nums.size();
        vector<string> ss(n);
        for (int i = 0; i < n; i++) ss[i] = to_string(nums[i]);
        sort(ss.begin(), ss.end(), [](const string& a, const string& b) {
            return a + b > b + a;
        });
        string result;
        for (const string& s : ss) result += s;
        int len = result.length(), k = 0;
        while (k < len - 1 && result[k] == '0') k++;
        return result.substr(k);
    }
};

Python 代码：

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums = list(map(str, nums))
        nums.sort(key=lambda x: x * 10, reverse=True)
        result = ''.join(nums)
        k = 0
        while k < len(result) - 1 and result[k] == '0': 
            k += 1
        return result[k:]

TypeScript 代码：

function largestNumber(nums: number[]): string {
    const ss = nums.map(num => num.toString());
    ss.sort((a, b) => (b + a).localeCompare(a + b));
    let result = '';
    for (const s of ss) result += s;
    let k = 0;
    while (k < result.length - 1 && result[k] === '0') k++;
    return result.substring(k);
};

• 时间复杂度：由于是对

进行排序，当排序对象不是

中的基本数据类型时，不会使用快排（考虑排序稳定性问题）。Java 中的 Arrays.sort 的底层实现会「元素数量/元素是否大致有序」决定是使用插入排序还是归并排序。这里直接假定使用的是「插入排序」。复杂度为

• 空间复杂度：

证明

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

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

上具有「全序关系」。

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

令我们经过这样的贪心操作得到的贪心解为

，真实最优解为

。

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

。

接下来我们只需要证明

，即可得

（贪心解即为最优解）。

我们使用「反证法」来证明

成立：

假设

不成立，即有

。

和

都是由同样一批数字凑成的，如果有

。

这意味着我们可以将

中的某些低位数字和高位数字互换，使得

更大（调整为

），这与我们根据「结果」进行排序的逻辑冲突。

因此

必然不成立，得证

成立，结合

可得贪心解为最优。

举个🌰，如果有

，那么意味着在

中至少有一对数字互换可以使得

变大，

那么在排序逻辑中

所在的整体（可能不只有

一个数）应该被排在

所在的整体（可能不只有

一个数）前面。

2. 全序关系

我们使用符号

来代指我们的「排序」逻辑：

• 如果

必须排在

的前面，我们记作

；

• 如果

必须排在

的后面，我们记作

；

• 如果

既可以排在

的前面，也可以排在

的后面，我们记作

；

2.1 完全性

具有完全性是指从集合

中任意取出两个元素

和

，必然满足

、

和

三者之一。

这点其实不需要额外证明，因为由

和

拼接的字符串

和

所在「字典序大小关系中」要么完全相等，要么具有明确的字典序大小关系，导致

必须排在前面或者后面。

2.2 反对称性

具有反对称性是指由

和

能够推导出

。

说明字符串

的字典序大小数值要比字符串

字典序大小数值大。

说明字符串

的字典序大小数值要比字符串

字典序大小数值小。

这样，基于「字典序本身满足全序关系」和「数学上的

和

可推导出

」。

得证

和

能够推导出

。

2.3 传递性

具有传递性是指由

和

能够推导出

。

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

和

必然是等长的。

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

：

然后我们只需要证明在不同的

关系之间（共三种情况），

恒成立即可：

1. 当

的时候：

1. 当

的时候：

1. 当

的时候：

综上，我们证明了无论在何种情况下，只要有

和

的话，那么

恒成立。

我们之所以能这样证明「传递性」，本质是利用了自定义排序逻辑中「对于确定任意元素

和

之间的排序关系只依赖于

和

的第一个不同元素之间的大小关系」这一性质。

找

的越界问题

考虑

(1) a = 304, b = 30

(2) a = 301, b = 30

两种情况。

显然，(1) 下我们会得到

，而 (2) 下我们会得到

但是，在这种情况下

实际上位于

界外，那我们还能不能找

呢？

是多少呢？

实际上是可以的。

我们在比较

和

的时候，实际上是在比较

和

两个字符串，所以实际上我们是在用

,

,

... 去填补

本体结束后的空缺。

换而言之 (1) 和 (2) 里的 b 实际上被填补为 303 （填进来

）

再比如 (3) a = 3131248, b = 3131

比较的时候实际上是用

开头的 4 位去填补上

的空缺，所以

实际上相当于 31313131

最后

在外工作的同学，除了记得吃 🥟，记得给家里打个电话