Java O(n), bit map + PQ


  • 0
    O

    Use a bitMap[256] to memorize the frequency of all occurred Letter; through a backward compareTo to offer Letter into a PriorityQueue<Letter>; build answer while polling from Queue<Letter>. Time complexity of O(n).

    public class Solution {
        public class Letter implements Comparable<Letter>{
    	public char c;
    	public int freq;
    	public Letter(char c) {
    	    this.c = c;
    	}
    	@Override
    	public int compareTo(Letter other) {
    	    return other.freq - this.freq;
    	}
        }
    	
        public String frequencySort(String s) {
            if (s == null || s.length() == 0) return "";
            int[] bitMap = new int[256];
            for (int i = 0; i < s.length(); i++) 
                bitMap[(int)s.charAt(i)]++;
            
            Queue<Letter> q = new PriorityQueue<Letter>();
            for (int i = 0; i < 256; i++) {
                if (bitMap[i] != 0) {
    	        Letter cur = new Letter((char) i);
    	        cur.freq = bitMap[i];
    	        q.offer(cur);
    	    }
            }
    	StringBuilder sb = new StringBuilder();
    	while (!q.isEmpty()) {
    	    Letter cur = q.poll();
    	    int freq = cur.freq;
    	    char c = cur.c;
    	    for (int i = 0; i < freq; i++)
    	        sb.append(c);
    	    }
    	return sb.toString();
        }
    }
    

  • 0
    S

    No way even to build a PriorityQ in O(n)


  • 0

    Totally wrong about time complexity.


Log in to reply
 

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