This problem is from LeetCode:
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.
The first simple solution is to treat each integer as string, sort the strings, then going through the strings in reversed lexicographical order and concatenate them all.
This approach works for some cases like: 99, 87, 34. Result is 998734.
However it doesn't work for [3, 30, 34, 5, 9], since it will generate 9534303 in stead of 9534330. So we need to make sure when we sort the array in a special way that "3" is larger than numbers like "30", "31", "32". Why? Because 330 > 303, 331>313...
How can we archive that? Actually the above comparison results already give us the hint! We can build a comparator, and concatenate the string in different ways and compared them.
Here is the code:
If we use Java8 stream API, without worrying about the all 0s case, this solution becomes a one-liner!!!
No comments:
Post a Comment