LeetCode 题解 – 179. 最大数(leetcode 最大子数组)

LeetCode 题解 - 179. 最大数(leetcode 最大子数组)

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

题目描述

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

示例 1:

LeetCode 题解 - 179. 最大数(leetcode 最大子数组)

示例 2:

LeetCode 题解 - 179. 最大数(leetcode 最大子数组)

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

​

解决方案

自定义排序:

想法

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

算法

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

如果仅按降序排序,有相同的开头数字的时候会出现问题。比方说,样例 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 题解 - 179. 最大数(leetcode 最大子数组)

Python 实现

LeetCode 题解 - 179. 最大数(leetcode 最大子数组)

复杂度分析

  • 时间复杂度:O(nlgn)

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

  • 空间复杂度:O(n)

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

本文作者:力扣

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至89291810@qq.com举报,一经查实,本站将立刻删除。
赞 (0)
上一篇 2024年4月4日 上午9:51
下一篇 2024年4月4日 上午9:57

相关推荐

  • 10月10日上学不

    10月10日上学,是一个熟悉又陌生的日期。对于很多人来说,这是一个普通的一天,但是对于某些人来说,这是一个特别的日子。在这一天,他们需要回到学校,开始新的学期。 这个学期,学生们将…

    教育百科 2025年8月24日
  • 学信网高考成绩单报告编号是什么

    学信网高考成绩单报告编号是什么? 学信网是教育部主管的一项教育信息化工作,旨在为高校学生和教师提供在线学习,考试,成绩管理和评价服务。高考成绩单是高校招生过程中重要的材料之一,学信…

    教育百科 2024年10月16日
  • 关于美育的材料作文(有关美育的高考作文素材积累)

    美育:培养审美素养,发掘创造力 美育是指通过培养人们的审美素养和创造力,来促进人的全面发展的教育。在现代社会,美育已经成为了一项非常重要的教育任务。那么,如何培养我们的美育素养和创…

    教育百科 2024年4月16日
  • 怎样限制孩子玩手机游戏制止孩子玩手机

    限制孩子玩手机游戏和制止孩子玩手机游戏都需要认真对待,因为它们可能会对孩子的健康和成长产生负面影响。以下是一些建议,以帮助限制孩子玩手机游戏和制止孩子玩手机游戏。 1. 制定规则并…

    教育百科 2024年10月10日
  • 小妹不上学

    小妹不上学 小妹是一个活泼可爱的孩子,但她却不想上学了。她曾经是一名优秀的学生,但是自从上了小学之后,她的成绩就开始下降,而且她的老师和同学们也开始对她产生不满和疏远。 小妹的父母…

    教育百科 2025年4月5日
  • 如何看待学生厌学

    如何看待学生厌学? 学生厌学是近年来备受关注的问题。对于这一问题,我们应该以理性的态度来看待。 首先,学生厌学可能是因为他们感到学习压力过大。当今社会,竞争日益激烈,许多学生感到自…

    教育百科 2025年7月22日
  • 为什么一二三后面是七个数字

    为什么一二三后面是七个数字? 在我们的日常生活中,我们经常使用数字来代表不同的事物。例如,我们使用1、2、3来表示三个数字,使用4、5、6来表示四个数字,以此类推。这些数字在我们的…

    教育百科 2024年11月10日
  • 湖南师范大学校花吴春怡,秀大长腿抢镜!甜美、性感、才艺她都有

    生活照 拍摄芭蕾写真,秀大长腿 生活照 参加访谈节目 甜美可人 和潮人李晨合影 健身 卖萌

    教育百科 2024年4月17日
  • 初三怎么休学保留学籍

    初三休学保留学籍的步骤如下: 1. 向学校提出申请。在申请休学之前,需要向学校提交一份书面申请,说明自己的情况以及想要休学的原因。学校将对其进行审查,决定是否批准申请。 2. 制定…

    教育百科 2024年11月4日
  • 爱玩游戏网(爱玩游戏平台)

    爱玩游戏平台: 一个让游戏爱好者欢聚一堂的地方 随着科技的不断发展,游戏已经成为人们生活中不可或缺的一部分。无论是在家中、办公室还是公共场所,人们总是可以看到人们在玩各种游戏。而今…

    教育百科 2024年4月1日

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注