首页 > 编程语言 > 详细

把数组排成最小的数

时间:2019-10-25 11:17:47      阅读:76      评论:0      收藏:0      [点我收藏+]

二、题目

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。

1、思路

遇到这个题,全排列当然可以做,但是时间复杂度为O(n!)。在这里我们自己定义一个规则,对拼接后的字符串进行比较。
排序规则如下:
若ab > ba 则 a 大于 b, 例子:a=3 b=32 ab=332 ba=323 所以a大于b 下面的规则和这个比较方法一致
若ab < ba 则 a 小于 b,
若ab = ba 则 a 等于 b;
根据上述规则,我们需要先将数字转换成字符串再进行比较,因为需要串起来进行比较。比较完之后,按顺序输出即可。

2、编程实现

python
代码实现方案:

# -*- coding:utf-8 -*-class Solution:    def PrintMinNumber(self, numbers):        # write code here        ifnumbers is None:            return ""        lens = len(numbers)        if lens ==0 :            return ""        tmpNumbers = sorted(numbers,cmp=self.compare)        return int(‘‘.join(str(x)for x in tmpNumbers))    def compare(self,num1,num2):        t = str(num1)+str(num2)        s = str(num2)+str(num1)        if t>s:            return 1        elif t<s:            return -1        else:            return 0

更多技术资讯可关注:gzitcast

把数组排成最小的数

原文:https://www.cnblogs.com/heimaguangzhou/p/11736302.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!