Sort Characters By Frequency

Leave a comment

November 27, 2016 by oneOokay

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

这一题的解决方法还挺好想的:我用的是一个HashMap+PriorityQueue+Node class。

挺多种实现方法的,我们来一一理一理:

  1. HashMap + PriorityQueue + Node class: TimeComplexity: O(nlogn) [priority queue: enqueuing and dequeuing O(logn)]
    1. HashMap iterator:
      1. 如果只关心key的话就可以用for(T t : map.keySet())
      2. 如果只关心value的话就可以用for (T t: map.values())
      3. 如果要iterate全部:
        • for(Map.Entry<T,T> entry : map.entrySet())
          • entry.getKey()
          • entry.getValue()
        • Iterator<Map.Entry<T,T>> entries = map.entrySet().iterator()
          • while (entries.hasNext())
          • Map.Entry<T,T> entry = entries.next()
          • entry.getKey(); entry.getValue()
    2. PriorityQueue:
      • Initialization: Queue<T> queue = new PriorityQueue<T>(size, comparator)
      • Comparator:
        • Collections.reverseOrder()
        • customized comparator:
          • 如果return left – right:则按left和right的自然顺序进行排序(从小到大),小的先出来;
          • 如果return right – left:则按left和right的自然顺序相反进行排序(从大到小),大的先出来。
 private Comparator<T> comparator = new Comparator<T>(){
 public int compare(T left, T right){
 if (left != right){
 return left - right; 
 }
 return 0;
 }};
  1. 首先上面可以不用Node,可以直接用HashMap<Character, Integer>。于是在加入PriorityQueue的时候直接把map的entryset加入到queue中[qp.addAll(map.entrySet())];所以comparator也需要与map的entryset兼容。这样:
        PriorityQueue<Map.Entry<Character, Integer>> pq = 
new PriorityQueue<>(
            new Comparator<Map.Entry<Character, Integer>>() {
                @Override
                public int compare(Map.Entry<Character, Integer> a, 
Map.Entry<Character, Integer> b) {
                    return b.getValue() - a.getValue();
                }
            }
        );
        pq.addAll(map.entrySet());

其次:如果保证所有字符是ASCII的话,那么可以用一个char[256]来代替HashMap

  • freq[ch]
  • (char)i

然后一个BucketSort:

  • 一个int[256]来存frequency
  • 一个String[]来存frequency为i的character
public class Solution {
 public String frequencySort(String s) {
 if (s == null || s.length() == 0) {
 return s;
 }
 
 int[] freq = new int[256];
 int max = 0;
 for (int i = 0; i < s.length(); i ++){
 freq[s.charAt(i)] ++;
 max = Math.max(max, freq[s.charAt(i)]);
 }
 String[] buckets = new String[max + 1];
 for (int i = 0; i < 256; i ++){
 if (freq[i] > 0){
 if (buckets[freq[i]] == null){
 buckets[freq[i]] = "";
 }
 buckets[freq[i]] = buckets[freq[i]] + (char)i; }} //这里只放入不同的character

 StringBuilder sb = new StringBuilder();
 for(int i = max; i >= 0; i --){
 if (buckets[i] != null){
 for (char ch : buckets[i].toCharArray()){
 for (int j = 0; j < i; j ++){
 sb.append(ch);//在这里根据frequency放入所有的characters
 }}}}
 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

%d bloggers like this: