Problem
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.
OR
As the last question of a successful interview, your boss gives you a few pieces of paper with numbers on it and asks you to compose a largest number from these numbers. The resulting number is going to be your salary, so you are very much interested in maximizing this number. How can you do this?
Example
Example 1:
|
|
Example 2:
|
|
Note: The result may be very large, so you need to return a string instead of an integer.
Solution
Method 1 - Using Sorting
If the nums
were single-digit number, then it would have been easy to just follow the algorithm:
|
|
But nums
will have multi-digit number.
This problem will be solved by greedy. We should put higher number before lower one. For eg. 9
before 5
OR 9
before 34
, as that will give us 95
and 934
respectively. Also, when we have same digit numbers like 35
and 34
, then 35
should come before 34
.
This problem can be solve by simply sorting strings, not sorting integer. Sorting integers will make 34 before 9, which will break our case.
Define a comparator to compare strings by concat() right-to-left or left-to-right.
|
|
Apparently, case1 is greater than case2 in terms of value.
Video explanation
Here is the video explaining this method in detail. Please check it out:
Code
|
|
|
|
|
|