BiruLyu
7/28/2017 - 5:53 PM

179. Largest Number(#).java

``````public class Solution {
public String largestNumber(int[] nums) {
if(nums==null||nums.length==0) return "";
int n = nums.length;
String[] numStrings = new String[n];
for(int i=0; i<n; i++){
numStrings[i] = String.valueOf(nums[i]);
}
Arrays.sort(numStrings, (a,b)->(b+a).compareTo(a+b));
if(numStrings[0].charAt(0)=='0') return "0";
StringBuilder sb = new StringBuilder();
for(String numString:numStrings){
sb.append(numString);
}
return sb.toString();
}
}``````
``````public class Solution {
//mergesort
public String largestNumber(int[] nums) {
int n;
for(n=0;n<nums.length;n++)
{
if(nums[n]!=0)
break;
}
if(n==nums.length)
return new String("0");
mergesort(nums);
StringBuilder s = new StringBuilder();
for(int i=0;i<nums.length;i++)
{
s.append(nums[i]);
}
return s.toString();
}
public void mergesort(int[] A) {
int n = A.length;
if (n < 2)
return;
int mid = n / 2, i;
int[] l = new int[mid], r = new int[n - mid];
for (i = 0; i < mid; i++)
l[i] = A[i];
for (int j=0; j < r.length; j++)
r[j] = A[i++];
mergesort(l);
mergesort(r);
merge(l, r, A);
}

public void merge(int[] l, int[] r, int[] A) {
int x=l.length, y = r.length,i=0, j=0, k=0;
while(i<x && j<y)
{
if(compare(l[i],r[j]))
A[k++]=r[j++];
else
A[k++]=l[i++];
}
while(j<y)
A[k++]=r[j++];
while(i<x)
A[k++]=l[i++];
}
public boolean compare(int a, int b)
{
if(a == 0 && b!=0)
return true;
else if(a!=0 && b==0)
return false;
int i = (int)Math.log10(a)+1, j = (int)Math.log10(b)+1;
if(i==j && a<b)
return true;
else if(i==j && a>b)
return false;
else
return (a*Math.pow(10,j)+b) < (b*Math.pow(10,i)+a);
}
}``````
``````public class Solution {
public String largestNumber(int[] num) {
if(num == null || num.length == 0)
return "";

// Convert int array to String array, so we can sort later on
String[] s_num = new String[num.length];
for(int i = 0; i < num.length; i++)
s_num[i] = String.valueOf(num[i]);

// Comparator to decide which string should come first in concatenation
Comparator<String> comp = new Comparator<String>(){
@Override
public int compare(String str1, String str2){
String s1 = str1 + str2;
String s2 = str2 + str1;
return s2.compareTo(s1); // reverse order here, so we can do append() later
}
};

Arrays.sort(s_num, comp);
// An extreme edge case by lc, say you have only a bunch of 0 in your int array
if(s_num[0].charAt(0) == '0')
return "0";

StringBuilder sb = new StringBuilder();
for(String s: s_num)
sb.append(s);

return sb.toString();

}
}``````