算法第二十二天-最大数

最大数

题目要求

解题思路

今天的题目,让我们将一组数字重新组合,构成一个最大的整数。由于构成的整数非常大,所以返回结果需要字符串格式。
分析一下规律:

  • 为了避免用int型或者long型越界,所以我们需要把数字先转换成字符串。然后可以把待比较的两个数字x,y组合成两个新的数字string(x)+string(y)string(y)+string(x),比较一下哪种组合构成的数字更大。

首先**拼接成的两个字符串一定是等长的。**等长的字符串在比较的时候,是按照字符串的各个字符从前向后逐个比较的,所以相当于先比较了百分位,然后比较十分位,最后比较个位。所以在字符串等长的情况下,字符串大,那么对应的整形也更大。但两个不等长的字符串就没有这个结论了。

综上,我们按照下面的步骤:
1.先把nums中的所有数字转字符串,形成字符串数组nums_str
2.比较两个字符串x,y拼接结果x+yy+x哪个更大,从而确定xy谁排在前面,讲nums_str降序排列;
3.把整个数组排序的结果拼接成一个字符串,并返回。

代码

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        from functools import cmp_to_key
        key = cmp_to_key(lambda x,y: int(y+x)-int(x+y))
        res = ''.join(sorted(map(str, nums), key=key)).lstrip('0')
        return res or '0'

 def bi(i):
     if i == 0:
         return 0
     s = 0
     k = i
     while i >= 1  :
         i=i/ 10
         s+=1
     return k /( 10 **s -1)
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
         nums=sorted(nums,key=bi,reverse=True)
         if nums[0] == 0:
             return "0"
         print(nums)
         return "".join([str(i) for i in nums])

复杂度分析

时间复杂度: O ( N ∗ l o g ( N ) ) O(N* log(N)) O(Nlog(N))
空间复杂度: O ( N ) O(N) O(N)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/340801.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

独立服务器有哪些优势

建立和维护一个强大的线上网站存在对于个人、企业和组织来说至关重要。而作为构建一个稳定、高效网站的基石之一,服务器的选择变得越来越重要。在服务器的选择中,独立服务器已经成为了许多人首选的方案。 独立服务器究竟有哪些优势呢? 1、稳…

拦截器与过滤器

拦截器(Interceptor)是一种特殊的组件,它可以在请求处理的过程中对请求和响应进行拦截和处理。拦截器可以在请求到达目标处理器之前、处理器处理请求之后以及视图渲染之前执行特定的操作。拦截器的主要目的是在不修改原有代码的情况下&#x…

常用芯片学习——HC245芯片

HC245三态输出八路总线收发器 使用说明 这些八路总线收发器专为数据总线之间的异步双向通信而设计。控制功能实现可更大限度地减少外部时序要求。根据方向控制 (DIR) 输入上的逻辑电平,此类器件将数据从 A 总线发送至 B 总线,或者将数据从 B 总线发送至…

macOS Sonoma 14.3RC(23D56)发布

系统介绍 黑果魏叔1 月18日消息,苹果今日向 Mac 电脑用户推送了 macOS 14.3 RC 更新(内部版本号:23D56),本次更新距离上次发布隔了 41 天。 如何升级 iOS / iPadOS / watchOS / macOS 开发版和公测版? 升…

【数学建模】图论模型

文章目录 图的基础理论及networkx简介图的基本概念图的表示及Networkx简介图的表示NetworkX简介 最短路算法及其Python实现固定起点到其余各点的最短路算法每对顶点间的最短路算法最短路应用 最小生成树算法及其networkx实现基本概念最小生成树算法最小生成树应用 匹配问题最大…

五、垃圾回收

1. 垃圾回收基础 1.1 什么是垃圾 简单说就是:内存中已经不再被使用到的内存空间就是垃圾。 1.2 如何判定是垃圾 1.2.1 引用计数法 引用计数法:给对象添加一个引用计数器,有访问就 1,引用失效就 -1 引用计数法的优缺点&#…

GIS项目实战10:MySQL数据库的安装与配置教程

MySQL是一个关系型数据库管理系统,由瑞典 MySQL AB 公司开发,属于 Oracle 旗下产品。MySQL是最流行的关系型数据库管理系统之一,在 WEB 应用方面,MySQL是最好的RDBMS (Relational Database Management System,关系数据…

2024年【黑龙江省安全员C证】免费试题及黑龙江省安全员C证作业考试题库

题库来源:安全生产模拟考试一点通公众号小程序 2024年【黑龙江省安全员C证】免费试题及黑龙江省安全员C证作业考试题库,包含黑龙江省安全员C证免费试题答案和解析及黑龙江省安全员C证作业考试题库练习。安全生产模拟考试一点通结合国家黑龙江省安全员C证…

根据音乐合成舞蹈;提升预训练扩散模型分辨率;基于扩散模型的视频超分;LLM推理加速框架;3D控制运动人像合成

本文首发于公众号:机器感知 根据音乐合成舞蹈;提升预训练扩散模型分辨率;基于扩散模型的视频超分;LLM推理加速框架;3D控制运动人像合成 DanceMeld: Unraveling Dance Phrases with Hierarchical Latent Codes for M…

架构篇11:架构设计流程-设计备选方案

文章目录 架构设计第 2 步:设计备选方案设计备选方案实战小结 上一期我讲了架构设计流程第 1 步识别复杂度,确定了系统面临的主要复杂度问题后,方案设计就有了明确的目标,我们就可以开始真正进行架构方案设计了。今天我来讲讲架构…

CVE重要通用漏洞复现java phpCVE-2021-44228

在进行漏洞复现之前我们需要在linux虚拟机上进行docker的安装 我不喜欢win上安因为不知道为什么总是和我的vmware冲突 然后我的kali内核版本太低 我需要重新安装一个新的linux 并且配置网络 我相信这会话费我不少时间 查看版本 uname -a 需要5.5或以上的版本 看错了浪…

理想斯特林循环空调

理想斯特林循环空调 淘汰传统的压缩机、摒弃现有的斯特林制冷机,理想斯特林循环制冷机是未来制冷空调领域的发展方向! 采用理想斯特林循环制冷机,是目前全球首创、国际领先、世界唯一、效率最高的斯特林制冷机。 取消了传统压缩机空调的蒸发器…

计算机视觉的应用

计算机视觉(Computer Vision)是一门研究如何让计算机能够理解和分析数字图像或视频的学科。简单来说,计算机视觉的目标是让计算机能够像人类一样对视觉信息进行处理和理解。为实现这个目标,计算机视觉结合了图像处理、机器学习、模…

接口测试 04 -- Jsonpath断言、接口关联处理

1. JsonPath基本介绍 1.1 JsonPath简介 JsonPath是一种用于在JSON数据中定位和提取特定数据的表达式语言。它类似于XPath用于XML的定位和提取,可以帮助我们灵活地从复杂的JSON结构中获取所需的数据。 1.2 JsonPath的特点 ● JsonPath可处理的报文类型为字典类型 …

【C语言深度剖析——第四节(关键字4)】《C语言深度解剖》+蛋哥分析+个人理解

追求本质,不断进步 本文由睡觉待开机原创,转载请注明出处。 本内容在csdn网站首发 欢迎各位点赞—评论—收藏 如果存在不足之处请评论留言,共同进步! 这里写目录标题 一、空间的申请1.变量定义1.1变量定义的概念:1.2变…

cuda二进制文件中到底有些什么

大家好。今天我们来讨论一下,相比gcc编译器编译的二进制elf文件,包含有 cuda kernel 的源文件编译出来的 elf 文件有什么不同呢? 之前研究过一点 tvm。从 BYOC 的框架中可以得知,前端将模型 partition 成 host 和 accel(accel 表…

日期处理第四篇(终)- Java日期时间处理大总结

文章目录 日期时间概念通用标准日期字段解析国际化的日期格式 日期的实战第一个问题:日期常用时间操作第二个问题:时区的问题时区概念时区的处理ZoneID的使用 ZoneOffset的使用让人恼火的夏令时 第三个问题:MySQL存储时间用什么类型&#xff…

HCIA——23DNS层次域名空间、域名服务器、域名解析的原理的选择、解答

学习目标: 计算机网络 1.掌握计算机网络的基本概念、基本原理和基本方法。 2.掌握计算机网络的体系结构和典型网络协议,了解典型网络设备的组成和特点,理解典型网络设备的工作原理。 3.能够运用计算机网络的基本概念、基本原理和基本方法进行…

【笔记】Blender4.0建模入门-3物体的基本操作

Blender入门 ——邵发 3.1 物体的移动 演示: 1、选中一个物体 2、选中移动工具 3、移动 - 沿坐标轴移动 - 在坐标平面内移动 - 自由移动(不好控制) 选中物体:右上的大纲窗口,点击物体名称,物体的轮…

LabVIEW电火花线切割放电点位置

介绍了一个电火花线切割放电点位置分布评价系统,特别是在系统组成、硬件选择和LabVIEW软件应用方面。 本系统由两个主要部分组成:硬件和软件。硬件部分包括电流传感器、高速数据采集卡、开关电源、电阻和导线。软件部分则由LabVIEW编程环境构成&#xf…