Easy to Understand O(n) Java Code


  • 0
    A
    public class Solution {
        public class Pair {
            char key;
            int val;
            
            public Pair(char key, int val){
                this.key = key;
                this.val = val;
            }
            
        }
        Comparator<Pair> comp = new Comparator<Pair>() {
            public int compare(Pair p1, Pair p2){
                return p2.val - p1.val;
            }
        };
        
        PriorityQueue<Pair> pq = new PriorityQueue<Pair>(10, comp);
        
        
        public String frequencySort(String s) {
            Map<Character, Integer> map = new HashMap<Character, Integer>();
            for(int i=0;i<s.length();i++){
                if(!map.containsKey(s.charAt(i))){
                    map.put(s.charAt(i), 1);
                } else {
                    map.put(s.charAt(i), map.get(s.charAt(i))+1);
                }
            }
            
            for(Map.Entry<Character, Integer> entry : map.entrySet()){
                Pair p = new Pair(entry.getKey(), entry.getValue());
                pq.add(p);
            }
            System.out.println(pq.size());
            StringBuilder result= new StringBuilder();
            // for(int i=0;i<pq.size();i++){
            while(!pq.isEmpty()){
                Pair p = pq.poll();
                System.out.println(p.key);
                for(int j=0;j<p.val;j++){
                    result.append(p.key);
                }
            }
            
            return new String(result);
        }
    }

Log in to reply
 

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