面试题45. 把数组排成最小的数

2020-05-15  本文已影响0人  周英杰Anita

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: "102"

示例 2:

输入: [3,30,34,5,9]
输出: "3033459"

提示:

0 < nums.length <= 100

说明:

输出结果可能非常大,所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0

思路:

此题本质上是一个排序问题。
排序判断规则: 设 nums任意两数字的字符串格式 x和 y,则
若拼接字符串 x + y > y + x ,则 m > n;
反之,若 x + y < y + x,则 n < m ;
根据以上规则,套用任何排序方法对 nums执行排序即可。
初始化: 字符串列表 strs,保存各数字的字符串格式;
列表排序:使用内置函数 functools.cmp_to_key(sort_rule),定义sort_rule排序由规则;
返回值: 拼接 strsstrs 中的所有字符串,并返回。

python3解法:

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def sort_rule(x, y):
            a = x + y
            b = y + x
            if a > b : return 1
            elif a < b : return  -1
            else: return 0
        strNums = [str(num) for num in nums]
        strNums.sort(key = functools.cmp_to_key(sort_rule))
        return ''.join(strNums)

链接:https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solution/mian-shi-ti-45-ba-shu-zu-pai-cheng-zui-xiao-de-s-4/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

上一篇 下一篇

猜你喜欢

热点阅读