leetcode算法题解题技巧(LeetCode题解)

leetcode算法题解题技巧(LeetCode题解)(1)

力扣 179. 最大数点击查看题目

题目描述

给定一组非负整数,重新排列它们的顺序使之组成一个最大的整数。

示例 1:

leetcode算法题解题技巧(LeetCode题解)(2)

示例 2:

leetcode算法题解题技巧(LeetCode题解)(3)

说明: 输出结果可能非常大,所以你需要返回一个字符串而不是整数。

解决方案

自定义排序:

想法

为了构建最大数字,我们希望越高位的数字越大越好。

算法

首先,我们将每个整数变成字符串。然后进行排序。

如果仅按降序排序,有相同的开头数字的时候会出现问题。比方说,样例 2 按降序排序得到的数字是 95343303,然而交换 3 和 30 的位置可以得到正确答案 9534330。因此,每一对数在排序的比较过程中,我们比较两种连接顺序哪一种更好。我们可以证明这样的做法是正确的:

假设(不是一般性),某一对整数 a 和 b,我们的比较结果是 a 应该在 b 前面,这意味着 a ⌢ b > b ⌢ a,其中 ⌢ 表示连接。如果排序结果是错的,说明存在一个 c,b 在 c 前面且 c 在 a 的前面。这产生了矛盾,因为 a ⌢ b > b ⌢ a 和 b ⌢ c > c ⌢ b 意味着 a ⌢ c > c ⌢ a。换言之,我们的自定义比较方法保证了传递性,所以这样子排序是对的。

一旦数组排好了序,最“重要”的数字会在最前面。有一个需要注意的情况是如果数组只包含 0,我们直接返回结果 0 即可。否则,我们用排好序的数组形成一个字符串并返回。

Java 实现

leetcode算法题解题技巧(LeetCode题解)(4)

Python 实现

leetcode算法题解题技巧(LeetCode题解)(5)

复杂度分析

  • 时间复杂度:O(nlgn)

尽管我们在比较函数中做了一些额外的工作,但是这只是一个常数因子。所以总的时间复杂度是由排序决定的,在 Python 和 Java 中都是 O(nlgn)。

  • 空间复杂度:O(n)

这里,我们使用了 O(n) 的额外空间去保存 nums 的副本。尽管我们就地进行了一些额外的工作,但最后返回的数组需要 O(n) 的空间。因此,需要的额外空间与 nums 大小成线性关系。


本文作者:力扣

声明:本文归“力扣”版权所有,如需转载请联系。

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页