179. Largest Number (Medium)
https://leetcode.com/problems/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.
Solutions
class Solution {
public String largestNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return "";
}
// 2276, 22
// 2272, 227
// 2273, 227
Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
// max common divisor
private int getMCD(int m, int n) {
if (m < n) {
int temp = m;
m = n;
n = temp;
}
while (m % n != 0) {
int temp = m % n;
m = n;
n = temp;
}
return n;
}
// least common multiple
private int getLCM(int m, int n) {
return m * n / getMCD(m, n);
}
@Override
public int compare(Integer o1, Integer o2) {
String str1 = o1 + "";
String str2 = o2 + "";
int len = getLCM(str1.length(), str2.length());
// FIXME following condition statement is totally wrong
// for (int i = 1; i < len / str1.length(); i++) {
while (str1.length() < len) {
str1 += o1;
}
// for (int i = 1; i < len / str2.length(); i++) {
while (str2.length() < len) {
str2 += o2;
}
for (int i = 0; i < len; i++) {
if (str1.charAt(i) > str2.charAt(i)) {
return -1;
}
if (str1.charAt(i) < str2.charAt(i)) {
return 1;
}
}
// the order doesn't matter if str1 == str2
return 1;
}
});
for (int i = 0; i < nums.length; i++) {
queue.add(nums[i]);
}
String ans = "";
while (!queue.isEmpty()) {
ans += queue.poll();
}
// FIXME, following express will lead to overflow
// remove invalid zeros, say "00", "000"
// return Integer.valueOf(ans) + "";
while (!ans.isEmpty() && ans.length() > 1) {
if (ans.charAt(0) != '0') {
break;
}
ans = ans.substring(1);
}
return ans;
}
}