Question
Formatted question description: https://leetcode.ca/all/179.html
179. Largest Number
Given a list of non negative integers, arrange them such that they form the largest number.
Example 1:
Input: [10,2]
Output: "210"
Example 2:
Input: [3,30,34,5,9]
Output: "9534330"
Note: The result may be very large, so you need to return a string instead of an integer.
@tog-top100
Algorithm
For two numbers a and b, if you convert them to strings, if ab> ba, then a will be ranked first,
- For example, 9 and 34, since 934>349, 9 is in front,
- For example, 30 and 3, because 303<330, 3 is in front of 30.
After sorting the original array according to this rule, converting each number into a string and then concatenating it is the final result.
Code
Java
import java.util.Arrays;
import java.util.Comparator;
public class Largest_Number {
class Solution {
public String largestNumber(int[] nums) {
// Get input integers as strings.
String[] asStrs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
asStrs[i] = String.valueOf(nums[i]);
}
// Sort strings according to custom comparator.
Arrays.sort(asStrs, new LargerNumberComparator());
// If, after being sorted, the largest number is `0`, the entire number
// is zero.
if (asStrs[0].equals("0")) {
return "0";
}
// Build largest number from sorted array.
String largestNumberStr = new String();
for (String numAsStr : asStrs) {
largestNumberStr += numAsStr;
}
return largestNumberStr;
}
private class LargerNumberComparator implements Comparator<String> {
@Override
public int compare(String a, String b) {
String order1 = a + b;
String order2 = b + a;
return order2.compareTo(order1);
}
}
}
}