剑指 Offer 45. 把数组排成最小的数

题目描述

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

示例 1:
输入: [10,2]
输出: "102"

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

提示:
0 < nums.length <= 100

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

解题思路

这个题本质上是一个排序问题，不过排序的大小比较对象是字符串而不是数字。具体判断规则如下图：

转换为python代码，可以用将数字转换为str以后相加，再转换为int以后比较大小。

def IsAGreaterThanOrEqualToB(self, a: int, b: int) -> bool:
        str_a = str(a)
        str_b = str(b)
        if int(str_a + str_b) >= int(str_b + str_a):
            return True
        else:
            return False

接下来只要将快速排序中的“≥”转换为上面的函数，就可以对整个数组进行排序。
一点小知识：快速将nums

解题代码

class Solution:
    def IsAGreaterThanOrEqualToB(self, a: int, b: int) -> bool:
        str_a = str(a)
        str_b = str(b)
        if int(str_a + str_b) >= int(str_b + str_a):
            return True
        else:
            return False

    def QuickSort(self, nums: list[int], low: int, high: int) -> list[int]:
        if low < high:
            pivot_pos = self.Partition(nums, low, high)
            self.QuickSort(nums, low, pivot_pos - 1)
            self.QuickSort(nums, pivot_pos + 1, high)
        return nums

    def Partition(self, nums: list[int], low: int, high: int) -> int:
        pivot_key = nums[low]
        while low < high:
            while low < high and self.IsAGreaterThanOrEqualToB(nums[high], pivot_key):
                high = high -1
            nums[low], nums[high] = nums[high], nums[low]
            while low < high and self.IsAGreaterThanOrEqualToB(pivot_key, nums[low]):
                low = low + 1
            nums[low], nums[high] = nums[high], nums[low]
        return low

    def minNumber(self, nums: list[int]) -> str:
        nums = self.QuickSort(nums, 0, len(nums)-1)
        nums = [str(i) for i in nums]
        result = "".join(nums)
        return result

执行结果

执行结果：通过
执行用时：56 ms, 在所有 Python3 提交中击败了33.27%的用户
内存消耗：15.2 MB, 在所有 Python3 提交中击败了16.73%的用户