给出一组非负整数,重新排序组成最大的数

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

描述

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

例
给出 [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 即可以测试。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户画像

7.6.2 内部排序算法的应用

1)若n较小(N<=50),则可以采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多,因而当记录本身信息量较大时,用简单选择排序...

701
来自专栏一直在跳坑然后爬坑

RxJava2操作符之“Scan”作用示例用法运行结果分析总结

扫描,遍历,用法和上一个Reduce操作符差不多,只是这个操作符会将每一个过程的中间产物发射出来,而不是只发射结果

943
来自专栏小小挖掘机

Numpy基础知识点汇总

1、概述 Numpy是高性能科学计算和数据分析的基础包,它的部分功能如下: 1)ndarray,一个具有矢量算术运算和复杂广播能力的快速且节省空间的多维数组。 ...

3174
来自专栏desperate633

LintCode 排颜色 II题目分析代码

给定一个有n个对象(包括k种不同的颜色,并按照1到k进行编号)的数组,将对象进行分类使相同颜色的对象相邻,并按照1,2,...k的顺序进行排序。

982
来自专栏Java技术栈

神奇,教你用随机数打印hello world

下面是一段随机数程序。 public static void main(String[] args) { System.out.println(rand...

3655
来自专栏分布式系统和大数据处理

正则表达式教程

1075
来自专栏机器学习之旅

tf.scan 记录

tf.scan(fn, elems, initializer=None, parallel_iterations=10, back_prop=True, swa...

1262
来自专栏java工会

java冒泡排序和快速排序

3033
来自专栏desperate633

LintCode A+B问题题目分析代码

给出两个整数a和b, 求他们的和, 但不能使用+等数学运算符。 ** 注意事项 ** ** 你不需要从输入流读入数据,只需要根据aplusb的两个参数a和b...

732
来自专栏大闲人柴毛毛

剑指 offer——面试题8求旋转数组的最小值

题目:将一个非递减序列的某一处切一刀,再把前半段序列放到后半段序列的后面,这样组成的新序列叫做“旋转数组”。要求获取一个旋转数组的最小值。 这本质上是一个求最值...

3476

扫码关注云+社区

领取腾讯云代金券