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

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

问题

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

示例 1:

输入: [10,2]
输出: “102”
示例 2:

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

提示:

0 < nums.length <= 100
说明:

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

分析

  1. 本质上要求返回的结果是一个升序序列；
  2. 与正常的排序算法的区别在于前者每次比较两个数值的大小，而此题比较的是两个字符串的大小；
  3. 确定比较规则，修改比较处的排序代码即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def quick_sort(nums):
            quick_sort_recursion(nums, 0, len(nums)-1)

        def quick_sort_recursion(nums, left, right):
            if left >= right: return 
            pivot_loc = partition(nums, left, right)
            quick_sort_recursion(nums, left, pivot_loc-1)
            quick_sort_recursion(nums, pivot_loc+1, right)
            
        def partition(nums, left, right):
            pivot = nums[left]
            while left < right:
                while left < right and nums[right] + pivot >= pivot + nums[right]: right -= 1 # 排序规则发生改变
                nums[left] = nums[right]
                while left < right and nums[left] + pivot <= pivot + nums[left]: left += 1 # 排序规则发生改变
                nums[right] = nums[left]
            nums[left] = pivot 
            return left 
        
        nums = [str(num) for num in nums]
        quick_sort(nums)
        return ''.join(nums)