JAVA priority queue O(N*logN) solution


  • 5
    O
    public class Solution {
        public static class LargetNumberComparator implements Comparator<String> {
    
            @Override
            public int compare(String s1, String s2) {
                String str1 = s1 + s2;
                String str2 = s2 + s1;
                return str2.compareTo(str1);
            }
        }
    
    
        public static String largestNumber(int[] nums) {
            PriorityQueue<String> queue = new PriorityQueue<String>(new LargetNumberComparator());
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < nums.length; i++){
                queue.add(String.valueOf(nums[i]));
            }
            boolean zero_f = true;
            while(!queue.isEmpty()){
                String tmp = queue.poll();
                if(!tmp.equals("0")) zero_f = false;
                sb.append(tmp);
            }
            if(zero_f) return "0";
            return sb.toString();
        }
    }
    

  • 0
    D

    Superb comparator! I was thinking more on lines of bucket sort comparator, but this is awesome!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.