[LC 451] Sort Characters By Frequency

sort numbers in a given range常用的思路: maintain an array for all possibilities, store the corresponding item into each element of the array. 通常可以用hashmap或treemap做的事情,例如记录每个key对应的value,或除了记录外还要将key排序等,都可以尝试用array做。Similar problem: [LC 347]Top K Frequent Elements. 如果用heap的话,1.只能保证最大值,不能保证整个序列sorted,2.一次insert一个number,有n个numbers,construct heap的time complexity是O(nlogn).

public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap();
        int maxCount = 0;
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
            maxCount = Math.max(maxCount, map.getOrDefault(c, 0));
        }
        // general solution for sorting numbers in a fixed range
        Set<Character>[] array = new Set[maxCount+1]; // new Set<Character>[] will be an error in compiling
        for (char c : map.keySet()) {
            int count = map.get(c);
            if (array[count] == null) {
                array[count] = new HashSet<Character>();
            }
            array[count].add(c);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = array.length-1; i>= 0; i–) {
            Set<Character> set = array[i];
            if (set == null) continue;
            for (char c : set) {
                for (int k = 0; k < i; k++) {
                    sb.append(c);
                }
            }
        }
        return sb.toString();
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s