Given a list of non negative integers, arrange them such that they form the largest number.
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.
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' else '0'