Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.
LeetCode-179: 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.
The problem is to find the largest number that can be formed by arranging the given numbers. The idea is to sort the numbers in such a way that the resulting number is the largest. This is done by comparing the strings formed by concatenating the numbers and sorting them in descending order.
Consider the example: [3,30,34,5,9]
3, 30 -> 330
30, 3 -> 303
330 > 303, the order is [3, 30]
3, 34 -> 334
34, 3 -> 343
334 < 343, the order is [34, 3]
34, 5 -> 345
5, 34 -> 534
345 < 534, the order is [5, 34]
5, 9 -> 59
9, 5 -> 95
59 < 95, the order is [9, 5]
and so-on; the final order is [9, 5, 34, 3, 30]
The numbers are sorted in the order: [9, 5, 34, 3, 30] which gives the largest number 9534330.
Here is a Java implementation of the approach:
public String largestNumber(int[] nums) {
String[] inputAsStringArray = Arrays.stream(nums)
.mapToObj(String::valueOf)
.toArray(String[]::new);
// Sort the numbers in descending order
// The comparison is done by concatenating the strings and comparing them
// in descending order
Arrays.sort(inputAsStringArray, (a, b) -> (b + a).compareTo(a + b));
// If the first number is 0, then the result is 0
if (inputAsStringArray[0].equals("0")) {
return "0";
}
// Concatenate the numbers to form the largest number
return Arrays.stream(inputAsStringArray).collect(Collectors.joining(""));
}
The time complexity for this approach is $O(n \cdot \log n)$ where $n$ is the number of elements in the input array. The space complexity is also $O(n)$ due to the space required to store the String representation of the input array.
Be notified of new posts. Subscribe to the RSS feed.