179. 最大数

Difficulty
Tags
URL
https://leetcode.cn/problems/largest-number/
Star
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例 1：
输入：nums = [10,2]输出："210"
示例 2：
输出："9534330"
提示：
  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 109

法1

思路：自定义比较算法，一般排序是比较数值大小，而本题目是比较 两个字符串两种拼接方式哪种会有更大的数值产生。
至于排序算法，归并和快排均可以
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums = [str(n) for n in nums]
        #nums = self.merge_sort(nums)
        self.quick_sort(nums, 0, len(nums)-1)
        nums = nums[::-1]
        # 去掉 开始的 0
        idx = 0
        while idx < len(nums)-1:
            if nums[idx] != "0":
                break
            idx += 1

        return "".join(nums[idx:])
        
    
    def quick_sort(self, nums, i, j):
        if i >= j:
            return
        
        idx = self.partition(nums, i, j)
        self.quick_sort(nums, i, idx-1)
        self.quick_sort(nums, idx+1, j)
    
    def partition(self, nums, s, e):
        temp_idx = random.randint(s, e)
        nums[temp_idx], nums[s] = nums[s], nums[temp_idx]
        
        povit = s
        l = s
        for r in range(l+1, e+1):
            if nums[r] + nums[povit] < nums[povit] + nums[r]:
                l += 1
                nums[l], nums[r] = nums[r], nums[l]
        nums[l], nums[povit] = nums[povit], nums[l]
        return l
                
        
        

    def merge_sort(self, nums):
        if len(nums) <= 1:
            return nums
        
        idx = len(nums) // 2
        left = self.merge_sort(nums[0:idx])
        right = self.merge_sort(nums[idx:])
        # print(left, right)
        return self.merge(left, right)
    
    def merge(self, l, r):
        res = []
        i, j = 0, 0
        while i < len(l) and j < len(r):
            # 第一个大于等于第二项
            if l[i] + r[j] > r[j] + l[i]:
                res.append(l[i])
                i += 1
            else:
                res.append(r[j])
                j += 1
        
        if i < len(l):
            res.extend(l[i:])
        if j < len(r):
            res.extend(r[j:])

        return res