Java 20ms O(n) bucket sort solution


  • 0
    protected class Node{
        public List<Character> ls;  //Store the characters with the same frequency .
        public Node(){
            ls = new ArrayList<>();
        }
    }
    public String frequencySort(String s) {
        int[] charCount = new int[256];
        char[] charArr = s.toCharArray();
        StringBuffer sb = new StringBuffer();
        Map<Integer, Node> freqRecord = new HashMap<>();
        for(char c:charArr){//O(n), count the presence of each character
            charCount[(int)c]++;
        }
        for(int i = 0;i<256;i++){//Add to the map, put all the characters with the same frequency into the same Node.
            if(charCount[i]!=0){
                if(freqRecord.containsKey(charCount[i])){
                    freqRecord.get(charCount[i]).ls.add((char) i);
                }
                else{
                    Node newNode = new Node();
                    newNode.ls.add((char) i);
                    freqRecord.put(charCount[i],newNode);
                }
            }
        }
        Arrays.sort(charCount); //Since charCount's size is fixed(256), this sort is O(1).
        int last = -1;
        for(int i = 255;i>=0;i--){//Reverse select
            if(charCount[i]!=last&&charCount[i]!=0){
                Node currNode = freqRecord.get(charCount[i]);
                for(char temp:currNode.ls){
                    int rest = charCount[i];
                    while(rest>0){
                        sb.append(temp);
                        rest--;
                    }
                }
                last = charCount[i];
            }
        }
        return sb.toString();
    }

Log in to reply
 

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