剑指Offer45-把数组排成最小的数
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"
示例 2:
输入: [3,30,34,5,9]
输出: "3033459"
提示:
- 0 < nums.length <= 100
说明:
输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
通过次数95,231提交次数169,529
来源：力扣（LeetCode）
链接：力扣
一解
设数组 nums 中任意两数字的字符串为 x 和 y ，若：
-
若拼接字符串 x + y > y + x ，则数组中 x 应该在 y 的右边
-
若 x + y < y + x ，则数组中 x 应该在 y 的左边
利用快排实现上述思路：
class Solution:
def minNumber(self, nums: List[int]) -> str:
def quick_sort(l, r):
if l >= r: return
i, j = l, r
while i < j:
# 一定要先从右边的哨兵开始遍历，因为取的 key 是 l
while str_nums[l] + str_nums[j] <= str_nums[j] + str_nums[l] and i < j: j -= 1
while str_nums[i] + str_nums[l] <= str_nums[l] + str_nums[i] and i < j: i += 1
str_nums[i], str_nums[j] = str_nums[j], str_nums[i]
str_nums[i], str_nums[l] = str_nums[l], str_nums[i]
quick_sort(l, i - 1)
quick_sort(i + 1, r)
str_nums = [str(i) for i in nums]
quick_sort(0, len(str_nums) - 1)
return "".join(str_nums)