Leetcode 179: Largest Number

https://leetcode.com/problems/largest-number/

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

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

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

 

Code

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        return ''.join(sorted(map(str, nums),cmp=lambda x,y:cmp(y+x, x+y))).lstrip('0') or '0'

 

Idea

Efficiently using `sorted` function makes the code very short. When concatenated string starts with zeros, you should strip all left zeros. The sort will take O(NlogN) time.

 

Reference:

https://leetcode.com/discuss/21550/my-3-lines-code-in-java-and-python