JZ45 把数组排成最小的数

发表于 分类于 本文字数： 548 阅读时长 ≈ 2 分钟

JZ45 把数组排成最小的数

题目描述

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

例如输入数组[3，32，321]，则打印出这三个数字能排成的最小数字为321323。

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

数据范围:$0<=len(numbers)<=100$

示例1

1
2
输入：[11,3]
返回值："113"

示例2

1
2
输入：[]
返回值：""

示例3

1
2
输入：[3,32,321]
返回值："321323"

题解

既然说把数组“排”成一个最小的数，那么排序肯定是少不了了的，但是如何进行这个排序是个问题，也就是说两个数字之间进行比较，让谁排在前面会让数字更小？

不需要考虑数位的问题，三位数和两位数相比较只比较两位即可，因为拼接之后的数位是一定的。

由此可以考虑两个数字进行比较，只需要逐位比较，直到找到某个数字的某一位比另一位大，则让大的排在后面，小的排在前面，如果所有的都相同，直到短数结束，将长的排在后面即可。

由此有了排序方式，再套上冒泡排序的壳，应该就可以AC了。

后来发现我简直是神经

正确的排序方式就是直接比较相邻两个字符串拼接之后的数字即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param numbers int整型一维数组 
# @return string字符串
#
class Solution:
    def sortRule(self,number1:int,number2:int) -> bool:
        str1 = str(number1)
        str2 = str(number2)
        if(''.join([str1,str2]) > ''.join([str2,str1])):
            return True
        else:
            return False
    def PrintMinNumber(self , numbers: List[int]) -> str:
        for i in range(len(numbers)):
            for j in range(i,len(numbers)):
                if(self.sortRule(numbers[i],numbers[j])):
                    temp = numbers[i]
                    numbers[i] = numbers[j]
                    numbers[j] = temp
        result = ''.join(str(num) for num in numbers)
        return result