179. Largest Number

    /*
     * 179. Largest Number
     * Difference be Comparator and Comparable
     * http://www.digizol.com/2008/07/java-sorting-comparator-vs-comparable.html
     * 排序思路：对于两个备选数字a和b，如果str(a) + str(b) > str(b) + str(a)，则a在b之前，
     * 按照此原则对原数组从大到小排序即可
     * 时间复杂度O（nlogn）
     * 这个题目我想到了priority queue的方法，但是没有想到具体什么样的方式来进行比较
     * 对于两个备选数字a和b，如果str(a) + str(b) > str(b) + str(a)，则a在b之前，否则b在a之前
     * 另外这里不是完全的priority queue
     * 而是用一个list来sort
     */
      public String largestNumber(int[] num) {
            if (num == null) {
                return null;
            }        
            ArrayList<Integer> list = new ArrayList<Integer>();
            for (int n1: num) {
                list.add(n1);
            }        
            Collections.sort(list, new Comparator<Integer>(){
                public int compare(Integer o1, Integer o2) {
                    String s1 = "" + o1 + o2;
                    String s2 = "" + o2 + o1;                
                    return s2.compareTo(s1);
                }
            });        
            StringBuilder sb = new StringBuilder();
            for (int n: list) {
                sb.append(n);
            }            
            if (sb.charAt(0) == '0') {    //注意细节问题，有0的话必须记住
                return "0";
            }        
            return sb.toString();
        }

 //自己的代码
public static String largestNumber(int[] nums) {
            int len=nums.length;
            if(nums==null||len==0)
              return " ";
             Queue<Integer> queue=new PriorityQueue<Integer>(len,
                  new Comparator<Integer>(){
                       public int compare(Integer l1,Integer l2){
                           String s1=Integer.toString(l1);
                           String s2=Integer.toString(l2);
                           String s1s2=s1+s2;
                           String s2s1=s2+s1;
                           int len=s1s2.length();
                           int i=0;
                           int j=0;
                           while(i<len&&j<len){
                               if(s1s2.charAt(i)-'0'>(s2s1.charAt(j)-'0')){
                                   return 1;
                               }
                               if(s1s2.charAt(i)-'0'<(s2s1.charAt(j)-'0')){
                                   return -1;
                               }
                               i++;
                               j++;
                           }
                           return 0;
                       }
                  }
             );
             for(int i=0;i<len;i++){
                 queue.offer(nums[i]);
             }
             StringBuffer sb=new StringBuffer();
             while(!queue.isEmpty()){
                 sb.insert(0,queue.poll());
             }
             if (sb.charAt(0) == '0') {    //注意细节问题，有0的话必须记住
                return "0";
            }    
             return sb.toString();
        }