|
二、题目 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{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 if numbers 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
| 
收藏
淘帖
踩
