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

benym

发布于 2022-07-14 15:24:59

2490

发布于 2022-07-14 15:24:59

文章被收录于专栏：后端知识体系

# LeetCode-面试题45-把数组排成最小的数

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

示例1：

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

示例2：

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

限制：

0 < nums.length <= 100

说明：

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

# 解题思路

排序：

对于两个数字m和n，可以拼接成mn和nm，如果mn<nm，那么就应该打印出mn，也就是m应该排在n之前，此时定义m"小于"n；反之，如果nm<mn，应该打印nm，此时定义n"小于"m；如果mn=nm，则n"等于"m，由于组合的数字很大，所以这也是一个大数问题，用字符串来进行拼接得到结果

在Java代码中可以重写Arrays中的compareTo接口，使x+y和y+x进行大小比较，sort方法默认升序，所以比较出来的数组自然是最小的

Python代码....原来还可以根据key自定义规则，方法来自https://leetcode-cn.com/u/bigkjp97/ (opens new window)因为默认升序，所以只需要改变大于或者小于的规则即可，其他规则富比较方法中不变不影响

# Java代码

class Solution {
    public String minNumber(int[] nums) {
        if(nums==null||nums.length==0)
            return "";
        String[] str = new String[nums.length];
        for(int i =0;i<nums.length;i++){
            str[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(str, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder res = new StringBuilder();
        for(String s:str)
            res.append(s);
        return res.toString();
    }
}

# Python代码1

class SmallerNumKey(str): # 定义一个类
    # 富比较方法
    def __lt__(x, y):
        return x + y < y + x

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        smallest_num = ''.join(sorted(map(str, nums),key=SmallerNumKey))
        return smallest_num

# Python代码2

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-05-06，如有侵权请联系 cloudcommunity@tencent.com 删除

python