[451]Sort Character by Frequency

Sort Character by Frequency

bucket sort

For this problem, each frequency should be bounded in 0-len. (len is the length of the string).
To achieve the O(n), use bucket sort.

To put the same character together, use a arraylist for each bucket unit.

import java.util.ArrayList;

public class Solution {
    public String frequencySort(String s) {
        ArrayList[] bucket = new ArrayList[s.length() + 1];

        int[] mp = new int[128];
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            mp[c]++;
        }

        for(int i = 0; i < mp.length; i++){
            int f = mp[i];
            if(f != 0){
                if(bucket[f] == null){
                    bucket[f] = new ArrayList<Integer>();
                }
                bucket[f].add(i);
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = bucket.length - 1; i > 0; i--){
            if(bucket[i] == null) continue;
            for(Object o : bucket[i]){
                int k = (Integer)o;
                for(int j = 0; j < i; j++){
                    sb.append((char)k);
                }

            }
        }

        return sb.toString();


    }
}

notes about generics

For this bubble sort, it use some generics array. see the reference.
generics gotcha