java solution with time O(nlogn) space O(n)


  • 0
    E
    public class Solution {
        public String frequencySort(String s) {
            // sanity check
            if (s == null || s.length() == 0) {
                return s;
            }
            Map<Character, Integer> map = new HashMap<>();
            PriorityQueue<Pair> maxHeap = new PriorityQueue<>(11, new Comparator<Pair>() {
                @Override
                public int compare(Pair a, Pair b) {
                    if (a.value == b.value) {
                        return 0;
                    }
                    return a.value > b.value ? -1 : 1;
                }
            });
            for (int i = 0; i < s.length(); i++) {
                Integer temp = map.get(s.charAt(i));
                if (temp == null) {
                    map.put(s.charAt(i), 1);
                } else {
                    map.put(s.charAt(i), temp + 1);
                }
            }
            
            for (Map.Entry<Character, Integer> m : map.entrySet()) {
                maxHeap.offer(new Pair(m.getKey(), m.getValue()));
            }
            StringBuilder sb = new StringBuilder();
            while (!maxHeap.isEmpty()) {
                Pair temp = maxHeap.poll();
                for (int i = 0; i < temp.value; i++) {
                    sb.append(temp.key);
                }
            }
            return sb.toString();
        }
        
        static class Pair {
            char key;
            int value;
            public Pair(char key, int value) {
                this.key = key;
                this.value = value;
            }
        }
    }
    

Log in to reply
 

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