最大数

[编程题]最大数

热度指数：38698 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为n的数组nums，数组由一些非负整数组成，现需要将他们进行排列并拼接，每个数不可拆分，使得最后的结果最大，返回值需要是string类型，否则可能会溢出。

数据范围： $1 \le n \le 100$ ， $0 \le nums[i] \le 10000$

进阶：时间复杂度 $O(nlogn)$ ，空间复杂度： $O(n)$

示例1

输入

[30,1]

输出

"301"

示例2

输入

[2,20,23,4,8]

输出

"8423220"

示例3

输入

[2]

输出

"2"

示例4

输入

[10]

输出

"10"

备注:

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

算法知识视频讲解

Python3

今天也要学习

遇到拼接字符串比较，就用cmp_to_key 方法，自定义比较规则

from functools import cmp_to_key
class Solution:
    def solve(self , nums: List[int]) -> str:
        def compare(x,y):
            if x+y > y+x:
                return -1
            elif x+y < y+x:
                return 1
            return 0

        nums_str = list(map(str,nums))
        nums_str.sort(key=cmp_to_key(compare))
        res = ''.join(nums_str).lstrip('0')
        return res if res else '0'

发表于 2025-01-06 16:45:56 回复(0)

Python3

是你的浩哥啊

利用冒泡排序进行组合的数字大小比较

class Solution:

def solve(self , nums ):
# write code here
if sum(nums)==0:
return 0
for i in range(len(nums) - 1):
for j in range(i + 1, len(nums)):
if int(str(nums[i]) + str(nums[j])) < int(str(nums[j]) + str(nums[i])):
nums[i], nums[j] = nums[j], nums[i]
return ''.join(str(i) for i in nums)

发表于 2021-10-18 20:18:09 回复(0)

Python3

牛客606997114号

#
# 最大数
# @param nums int整型一维数组
# @return string字符串
#
class Solution:
def solve(self , nums ):
# write code here
l = len(str(max(nums)))
s = ''.join(sorted(map(str,sorted(nums)), key=(lambda x:x.ljust(l,x[0])), reverse=True))
if s[0]=='0':
return '0'
return s

发表于 2021-08-09 14:57:05 回复(0)