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)`` 峰值空间。