给出一组非负整数，重新排列他们的顺序把他们组成一个最大的整数。

VincentFF 发布于2019-07-30 16:09 / 3909人阅读

摘要：文章为原创首发地址描述给出一组非负整数，重新排列他们的顺序把他们组成一个最大的整数。算法每个元素逐个字符进行对比。代码代码测试以上代码已放到的上开源，欢迎或提建议。运行即可以测试。

文章为原创首发地址：https://hooyes.net/p/python-l...

描述

给出一组非负整数，重新排列他们的顺序把他们组成一个最大的整数。

例
给出 [1, 20, 23, 4, 8]，返回组合最大的整数应为 8423201
给出 [1, 201, 20, 9, 8]，返回组合最大的整数应为 98202011
给出 [1, 203, 20, 9, 8]，返回组合最大的整数应为 98203201

算法

我给简单好理解的两个排序算法：

算法1：

先把对比的数字转成字符，拼接后再转成整数进行大小对比，即 int(a+b) 与 int(b+a) 进行降序排列。代码1。

算法2：

每个元素逐个字符进行对比。代码2。

代码1

# Python2

class Solution:
    def largestNumber(self, nums):
        scmp = lambda a,b: int(b+a)-int(a+b)
        res = "".join(sorted(map(str, nums), cmp=scmp)).lstrip("0")
        return res or "0"

# Python3 

from functools import cmp_to_key
class Solution:
    def largestNumber(self, nums):
        key = cmp_to_key(lambda a,b: int(b+a)-int(a+b))
        res = "".join(sorted(map(str, nums), key=key)).lstrip("0")
        return res or "0"

代码2

# Python2 

class Solution:
    def largestNumber(self,nums):
        def cxx(x,y):
            i = 0 
            sx= str(x)
            sy= str(y)
            while i< len(str(min(x,y))):
                if sx[i] > sy[i]:
                    return 1
                elif sx[i] < sy[i]:
                    return -1
                elif x == y:
                    return 0
                i+=1
            if i == len(sx):
                return -1 if sy[i]>sy[0] else 1
            if i == len(sy):
                return 1 if sx[i]>sx[0] else -1
        nx = sorted(nums,cmp=lambda x,y:cxx(x,y),reverse=True)        
        res = "".join(map(str, nx)).lstrip("0")
        return res or "0"

测试

t = Solution()
print(t.largestNumber([1, 20, 23, 4, 8]))
// 8423201

以上代码已放到Hooyes的Github上开源，欢迎Fork或提建议。

largest-number.py

运行 python largest-number.py 即可以测试。

GPU云服务器云服务器他们之间 js随机一个整数 java中的整数除 c语言整数的存储形式

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/41520.html

LeetCode 179. 最大数【c++/java详细题解】

摘要：示例输入输出示例输入输出示例输入输出示例输入输出思路贪心给定一组非负数，重新排列使其组成一个最大的整数。具体过程如下自定义排序规则函数，将数组按照自定义排序规则重新排序。时间复杂度分析排序的时间复杂度为。 ...

tuantuan 2021-09-02 15:15 评论0 收藏0
小李飞刀：刷题第十三弹！

摘要：写在前面今天的小李的目标是排序算法，果然还是要下手写才会更有体会，也更记得住。排序算法冒泡排序主要是比对相邻两个数之间的大小关系，不断将较大值交换至最后。写在前面今天的小李的目标是排序算法，果然还是要下手写才会更有体会，也更记得住。认真做题的分割线第一题 215. 数组中的第K个最大元素难度：中等在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的...

lixiang 2019-07-31 10:20 评论0 收藏0
犀牛书——CHAP7：数组

摘要：数组有以下特点无类型数组元素可以是任意元素。因此，当小于数组最大索引时，大于的数组元素会被删除。原数组不会改变将数组元素转换为字符串并连接在一起。默认将数组元素用，连接，传入的参数即为连接符。 showImg(https://box.worktile.com/view/fcfcdf2c99b14edfb6768085955ae253?pid=4b0845b09ca94218a955f8...

Alfred 2019-08-19 18:40 评论0 收藏0
小李飞刀：做题第十一弹！

摘要：第五题对称二叉树难度简单给定一个二叉树，检查它是否是镜像对称的。第十六题最大连续的个数难度简单给定一个二进制数组，计算其中最大连续的个数。第十八题平方数之和难度简单给定一个非负整数，你要判断是否存在两个整数和，使得。写在前面最近忙着调教新装备，没有及时的写题解，但是没有在偷懒没刷题喔~来认真整理下最近做的题目~ 之前考虑按tag来刷题，后来收到了推荐的leetcode题解，就根据上...

ytwman 2019-07-31 10:18 评论0 收藏0
LeetCode 213. 打家劫舍 II【c++/java详细题解】

摘要：给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。状态表示表示偷窃号到号房间所能获得的最高金额。下标均从开始打家劫舍我们已经知道了房间单排排列的状态转移方程，接下来思考房间环状排列的做法。 ...

Kyxy 2021-09-23 11:21 评论0 收藏0