Largest Number
Total Accepted: 2269
Total Submissions: 15366
Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is9534330.
Note: The result may be very large, so you need to return a string instead of an integer.
[分析]
按题目的要求, 重写排序方法, 然后排序便可.
[注意]
当1个数是另外一个数的前缀时, 要注意顺序. 这里用了个小技能 比较 S1+S2 ? S2+S1 便可.
另外, leading zeros要去掉.
[CODE]
second try:
public String largestNumber(int[] arr) {
Integer[] array = new Integer[arr.length];
int i = 0;
for (int value : arr) {
array[i++] = Integer.valueOf(value);
}
Arrays.sort(array, new Comparator<Integer>() {
@Override
public int compare(Integer a1, Integer a2) {
int l1 = a1==0? 1 : (int) Math.log10(Math.abs(a1)) + 1;
int l2 = a2==0? 1 : (int) Math.log10(Math.abs(a2)) + 1;
long aa1 = (long) (a1 * Math.pow(10, l2) + a2);
long aa2 = (long) (a2 * Math.pow(10, l1) + a1);
return aa1>aa2 ? ⑴ : (aa1==aa2 ? 0 : 1);
}
}
);
StringBuilder sb = new StringBuilder();
for(Integer e : array) {
sb.append(e);
}
return sb.toString().replaceFirst("^0+(?!$)", "");
}
}
first edition:
public String largestNumber(int[] arr) {
String[] strs = new String[arr.length];
for(int i=0; i<arr.length; i++) {
strs[i] = Integer.toString(arr[i]);
}
Arrays.sort(strs, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
String ss1 = s1 + s2;
String ss2 = s2 + s1;
int i=0;
while(i<ss1.length()) {
if(ss1.charAt(i)!=ss2.charAt(i)) {
return ss1.charAt(i) – ss2.charAt(i);
}
++i;
}
return 0;
}
}
);
StringBuilder sb = new StringBuilder();
for(int i=strs.length⑴; i>=0; i–) {
sb.append(strs[i]);
}
return sb.toString().replaceFirst("^0+(?!$)", "");
}
}
波比源码 » leetcode 179: Largest Number
