最大负整数是啥,最大的负整数是1 对吗

首页 > 教育 > 作者:YD1662024-05-10 14:49:11

最大负整数是啥,最大的负整数是1 对吗(1)

179. 最大数点击查看题目

题目描述

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

示例 1:

最大负整数是啥,最大的负整数是1 对吗(2)

示例 2:

最大负整数是啥,最大的负整数是1 对吗(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 实现

最大负整数是啥,最大的负整数是1 对吗(4)

Python 实现

最大负整数是啥,最大的负整数是1 对吗(5)

复杂度分析

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

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


本文作者:力扣

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

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.