Largest Number 184
Question
Given a list of non negative integers, arrange them such that they form the largest number.
Notice
The result may be very large, so you need to return a string instead of an integer.
Example
Given [1, 20, 23, 4, 8], the largest formed number is 8423201.
Challenge
Do it in O(nlogn) time complexity.
Solution
这道题很简单,只要利用排序把高位大的数排到前面即可。把int数转换成string,然后利用string的compareTo方法,比较s1+s2和s2+s1即可。最后只要注意把前置的0去掉。
代码如下:
public class Solution {
/**
*@param num: A list of non negative integers
*@return: A string
*/
class myComparator implements Comparator<Integer>{
public int compare(Integer a, Integer b){
String s1 = a.toString();
String s2 = b.toString();
return (s2 + s1).compareTo(s1 + s2);
}
}
public String largestNumber(int[] num) {
// write your code here
String res = "";
if(num == null || num.length == 0){
return res;
}
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(1, new myComparator());
for(int i = 0; i < num.length; i++){
queue.add(num[i]);
}
while(!queue.isEmpty()){
int curt = queue.poll();
if(res.length() == 0 && curt == 0 && !queue.isEmpty()){
continue;
}
res = res + curt;
}
return res;
}
}