首页 > itarticle > 179. largest number 解法

179. largest number 解法

admin 11月 12, 2020 0

179. Largest Number

Difficulty: Medium

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

Example 1:

1
2
 
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.

解法

自定义比较器

法一

Language: Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
import functools
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        strnums = [str(n) for n in nums]
        def mycmp(a, b):
            if a + b > b + a:
                return -1
            else:
                return 1
        strnums.sort(key = functools.cmp_to_key(mycmp))
        res = ''.join(strnums)
        if int(res) == 0:
            return "0"
        else:
            return res

法二

自定义可比较类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
class :
    
    def __init__(self, num):
        self.value = str(num)
    def __lt__(self, other):
        # '82' is before '824' because '82|824' is greater than '824|82'
        return self.value + other.value > other.value + self.value
    def __gt__(self, other):
        return self.value + other.value < other.value + self.value
    def __eq__(self, other):
        return self.value + other.value == other.value + self.value


class Solution:
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        numStrings = [Comparable(n) for n in nums]
        numStrings.sort()
        output = ''.join((e.value for e in numStrings))
        return output.lstrip('0') or '0'

法三

重载运算符

1
2
3
4
5
6
7
8
 
class LargerNumKey(str):
    def __lt__(x, y):
        return x+y > y+x
        
class Solution:
    def largestNumber(self, nums):
        largest_num = ''.join(sorted(map(str, nums), key=LargerNumKey))
        return '0' if largest_num[0] == '0' else largest_num
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能