[Leetcode]179. Largest Number

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

Logic

This question asks for the order to join all numbers together such that the output will be the largest one. The intuitive approach is that, if a.b > b.a, then a should be joined before b. This leads to O(n^2). However, observing that if a.b>b.a and b.c>c.b, then a.c>c.a (the proof is available here ), we can use O(nlogn) sorting algorithms with self-defined comparing methods.

Code

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        def tcmp(n1,n2):
            if n1+n2 > n2+n1:
                return -1
            return 1
        nums = sorted(list(map(str,nums)),key=cmp_to_key(tcmp))
        return ''.join(nums) if nums[0] != '0' else '0' 

Reference

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments