Java easy understand solution using Map + PriorityQueue


  • 0
    F
    class Entry {
    	char c;
    	int f;
    
    	public Entry(char ch, int frequency) {
    		c = ch;
    		f = frequency;
    	}
    }
    
    class myCompare implements Comparator<Entry> {
    	public int compare(Entry e1, Entry e2) {
    		return e2.f - e1.f;
    	}
    }
    
    public String frequencySort(String s) {
    	PriorityQueue<Entry> queue = new PriorityQueue<Entry>(new myCompare());
    	Map<Character, Entry> map = new HashMap<Character, Entry>();
    	for (int i = 0; i < s.length(); i++) {
    		char c = s.charAt(i);
    		Entry e;
    		if (!map.containsKey(c)) {
    			e = new Entry(c, 1);
    			map.put(c, e);
    		} else {
    			e = map.get(c);
    			e.f++;
    			queue.remove(e);
    		}
    		queue.add(e);
    	}
    	StringBuilder res = new StringBuilder();
    	while (!queue.isEmpty()) {
    		Entry e = queue.poll();
    		for (int i = 0; i < e.f; i++) {
    			res.append(e.c);
    		}
    	}
    	return res.toString();
    }

  • 0
    H

    Hey man great solution. Correct me if i'm wrong but this is in O(n) time and O(n) space right?


  • 0
    F

    @hgdangkhoi I think the time complexity should be O(nlogn).


Log in to reply
 

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