179. Largest Number
Greedy, Array, String, Sortin, Review ·Problem Statement
link: https://leetcode.com/problems/largest-number/ https://leetcode.cn/problems/largest-number/
Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.
Since the result may be very large, so you need to return a string instead of an integer.
Example:
Input: ` nums = [10,2]
**Output:** 210`
Input: ` nums = [3,30,34,5,9]
**Output:** “9534330”`
Solution Approach
The essence of this problem is to define a non-standard comparison between two numbers.
Algorithm
- Convert integers to strings.
- Craft a comparison rule: for two numbers a and b,if a + b > b + a comes first.
- Sort numbers using this rule.
- Join the sorted numbers. If the result starts with “0”, return “0”.
Implement
class Compare(str):
def __lt__(x, y):
return x + y < y + x
class Solution:
def largestNumber(self, nums: List[int]) -> str:
largest_num = ''.join(sorted(map(str, nums), key=Compare, reverse=True))
return '0' if largest_num[0] == '0' else largest_num
from functools import cmp_to_key
from typing import List
class Solution:
def largestNumber(self, nums: List[int]) -> str:
nums_str = list(map(str, nums))
def compare(x, y):
return (x + y > y + x) - (x + y < y + x)
nums_str.sort(key=cmp_to_key(compare), reverse=True)
res = "".join(nums_str)
if res[0] == "0":
res = "0"
return res
from functools import cmp_to_key
from typing import List
class Solution:
def largestNumber(self, nums: List[int]) -> str:
nums_str = list(map(str, nums))
def compare(x, y):
return (x + y > y + x) - (x + y < y + x)
sorted_strs = sorted(nums_str, key=cmp_to_key(compare), reverse=True)
res = "".join(sorted_strs)
if res[0] == "0":
res = "0"
return res