leetcode 179

发表于 | 分类于 ，
字数统计: | 阅读时长 ≈

179

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

1
2
3
Input: [10,2]
Output: "210"
Example 2:
1
2
Input: [3,30,34,5,9]
Output: "9534330"

Note: The result may be very large, so you need to return a string instead of an integer.

思路

关键点就在于，如何对比两个数的大小？（理解为两个数谁应该放在前面），解法是按照顺序拼接两个字母串进行比较，如果a ＋b串 大于 b＋a串，那么a比较大（即题意中理解的a应该放在前面），反之b比较大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        if len(nums)==0:
            return ""
        self.quickSort(nums,0,len(nums)-1)
        return str(int("".join(map(str, nums)))) 


    def compare(self,num1:int,num2:int):
        return str(num1)+str(num2)>str(num2)+str(num1)

    def quickSort(self,nums: List[int],low: int,high:int):
        if low >=high:
            return
        mid = self.adjust(nums,low,high)
        self.quickSort(nums,low,mid-1)
        self.quickSort(nums,mid+1,high)
    
    def adjust(self,nums: List[int],l:int,r:int) -> int:
        low = l
        while l < r:
            if self.compare(nums[l], nums[r]):
                nums[l], nums[low] = nums[low], nums[l]
                low += 1
            l += 1
        nums[low], nums[r] = nums[r], nums[low]
        return low