0179. Largest Number
====================
题目信息
--------
:题号: 0179. 最大数
:难度: Medium
:主题: 字符串、排序、自定义比较器、交换论证
:原题: `LeetCode 0179 `_
:重点: 将全排列压缩为两元素拼接顺序,用 a+b 与 b+a 决定局部次序并证明全局最优
题目重述
--------
给定非负整数数组 ``nums``,重新排列所有元素,将它们的十进制文本依次拼接,使结果尽可能
大。每个元素必须恰好使用一次,返回结果字符串。
完整结果可能超过固定宽度整数,所以不能以数值类型返回。若输入全为 0,规范结果是单个
``"0"``,不是带多个前导零的字符串。
自建示例
--------
.. code-block:: text
输入:nums = [3,30,34,5,9]
输出:"9534330"
排列顺序为 9、5、34、3、30;数值 30 虽大于 3,却必须放在 3 后面。
.. code-block:: text
输入:nums = [121,12]
输出:"12121"
"12" + "121" 大于 "121" + "12",所以 12 应在 121 前面。
.. code-block:: text
输入:nums = [0,0,0]
输出:"0"
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
public:
std::string largestNumber(std::vector& nums) {
std::vector parts;
parts.reserve(nums.size());
for (int value : nums) {
parts.push_back(std::to_string(value));
}
std::sort(
parts.begin(),
parts.end(),
[](const std::string& left, const std::string& right) {
return left + right > right + left;
});
if (parts.front() == "0") {
return "0";
}
std::size_t total_length = 0;
for (const std::string& part : parts) {
total_length += part.size();
}
std::string answer;
answer.reserve(total_length);
for (const std::string& part : parts) {
answer += part;
}
return answer;
}
};
题解
----
原始搜索空间是全部排列
~~~~~~~~~~~~~~~~~~~~~~
按照题意,可以生成 ``n!`` 个元素排列,逐个拼接并取最大字符串。它不会遗漏答案,但每次
排列只改变少数相对顺序,大量前后片段被重复构造和比较。瓶颈是没有回答更基本的问题:
任取两个元素 ``a``、``b``,它们谁在前面更有利?
普通数值降序不能回答。对 3 与 30,数值上 30 更大,但 ``330 > 303``,所以 3 必须在
前。普通字符串字典序也不足:``"121"`` 因为是 ``"12"`` 的更长前缀会被排在前面,
但 ``12112 < 12121``,正确顺序恰好相反。
两元素的完整比较
~~~~~~~~~~~~~~~~
固定排列中其余元素,只比较相邻的 ``a``、``b``。两种候选结果拥有相同的外部前缀和
后缀,差异只在中间块:
.. code-block:: text
... + a + b + ...
... + b + a + ...
因此若 ``a + b > b + a``,就让 ``a`` 排在 ``b`` 前面。两个拼接串长度相同且都只含
十进制数字,字符串字典序与它们代表的大整数顺序一致;无需把可能溢出的拼接结果转换成
整数。
示例中:
.. code-block:: text
3 与 30: "330" > "303",所以 3 在前
12 与 121:"12121" > "12112",所以 12 在前
这个规则比较的是完整交叉拼接,不是首字符、更长文本或数值大小等局部特征。
比较器为何可以交给排序
~~~~~~~~~~~~~~~~~~~~~~
可以把每个非空字符串无限重复,例如 ``"12"`` 变成 ``121212...``。比较
``a + b`` 与 ``b + a`` 的结果,等价于比较 ``a``、``b`` 两个无限周期串的字典序:
第一处不同字符会在一个共同周期内出现;若永远没有差异,则 ``a+b == b+a``。
无限字符串字典序具有传递性和不对称性,相同周期串形成等价类,所以
``a+b > b+a`` 是 ``std::sort`` 可以使用的严格弱序。等价元素无论谁在前,局部拼接都
相同,不需要稳定排序。
局部顺序为何得到全局最大
~~~~~~~~~~~~~~~~~~~~~~~~~~
假设某个排列含相邻逆序 ``b,a``,而比较器认为 ``a+b > b+a``。交换这两个元素时,
排列的公共前缀和后缀完全不变,中间块从 ``b+a`` 变为更大的 ``a+b``,所以完整结果严格
增大。
不断交换逆序相邻对,有限步后得到比较器排序结果,过程中拼接值只增不减。任意初始排列
都能这样转成排序结果,因此排序结果不小于任何排列,也就是全局最大值。排序一次就取代了
对全部排列的重复构造。
代码状态走读
~~~~~~~~~~~~
``parts`` 先保存所有十进制文本,避免排序比较时反复调用 ``to_string``。排序后的数组已
满足每个相邻对都采用更优拼接顺序,最终只需从左到右追加。
``answer.reserve(total_length)`` 先计算结果总长度并预留空间,减少字符串增长时的重复
扩容;它不参与正确性,只删除构造阶段的内存搬移。
排序后若首项是 ``"0"``,就不可能还有正数:任何正数字符串与 ``"0"`` 比较时都会
排在它前面。因此所有元素必为 0,直接返回 ``"0"``,避免产生 ``"000"``。不能无条件
删除前导零,因为每个原始非零数的文本本来就没有前导零,只有全零输入需要归一化。
复杂度
~~~~~~
设元素数为 ``n``,单个数字文本最大长度为 ``k``,全部文本总长度为 ``D``。转换与最终
拼接需要 ``O(D)`` 时间;排序进行 ``O(n log n)`` 次比较,每次构造并比较长度至多
``2k`` 的拼接串,时间上界为 ``O(n k log n)``。字符串数组和答案占 ``O(D)`` 空间,
比较器产生的临时拼接串占 ``O(k)`` 峰值空间。