Leetcode 451. Sort Characters By Frequency 按频率对字符排序

78 阅读 0 评论 52 点赞

我是靠谱客的博主壮观日记本，最近开发中收集的这篇文章主要介绍Leetcode 451. Sort Characters By Frequency 按频率对字符排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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.

Bucket Sort + HashMap

 1 public class Solution {
 2     public String frequencySort(String s) {
 3         Map<Character, Integer> map = new HashMap<>();
 4         for (char c : s.toCharArray()) {
 5             if (map.containsKey(c)) {
 6                 map.put(c, map.get(c) + 1);
 7             } else {
 8                 map.put(c, 1);
 9             }
10         }
11         List<Character> [] bucket = new List[s.length() + 1];
12         for (char key : map.keySet()) {
13             int frequency = map.get(key);
14             if (bucket[frequency] == null) {
15                 bucket[frequency] = new ArrayList<>();
16             }
17             bucket[frequency].add(key);
18         }
19         StringBuilder sb = new StringBuilder();
20         for (int pos = bucket.length - 1; pos >=0; pos--) {
21             if (bucket[pos] != null) {
22                 for (char num : bucket[pos]) {
23                     for (int i = 0; i < map.get(num); i++) {
24                         sb.append(num);
25                     }
26                 }
27             }
28         }
29         return sb.toString();
30     }
31 }

HashMap+ Heap+Wrapper Class

 1 public class Solution {
 2     public String frequencySort(String s) {
 3         PriorityQueue<WrapperChar> maxheap = new PriorityQueue(1, new Comparator<WrapperChar>() {
 4             public int compare(WrapperChar w1, WrapperChar w2) {
 5                 return w2.count - w1.count;
 6             }
 7         });
 8         HashMap<Character, WrapperChar> map = new HashMap<Character, WrapperChar>();
 9         for (int i=0; i<s.length(); i++) {
10             char c = s.charAt(i);
11             if (!map.containsKey(c)) map.put(c, new WrapperChar(c, 1));
12             else {
13                 int newCount = map.get(c).count + 1;
14                 map.put(c, new WrapperChar(c, newCount));
15             }
16         }
17         for (char c : map.keySet()) maxheap.offer(map.get(c));
18         StringBuilder res = new StringBuilder();
19         while (!maxheap.isEmpty()) {
20             WrapperChar wChar = maxheap.poll();
21             for (int i=0; i<wChar.count; i++) {
22                 res.append(wChar.c);
23             }
24         }
25         return res.toString();
26     }
27     
28     public class WrapperChar {
29         char c;
30         int count;
31         public WrapperChar(char ch, int num) {
32             this.c = ch;
33             this.count = num;
34         }
35     }
36 }

class Solution {
    class MyComparator implements Comparator {

        @Override
        public int compare(Object o1, Object o2) {
            Map.Entry e1 = (Map.Entry) o1;
            Map.Entry e2 = (Map.Entry) o2;

            // Reverse
            return (int)e2.getValue() - (int)e1.getValue();
        }
    }

    public String frequencySort(String s) {
        Map<String, Integer> mp = new HashMap<>();
        for (int i=0; i<s.length(); i++) {
            String key = s.substring(i, i+1);
            if (mp.containsKey(key)) {
                mp.put(key, mp.get(key)+1);
            }
            else {
                mp.put(key, 1);
            }
        }

        List<Map.Entry> lst = new ArrayList<>(mp.entrySet());
        Collections.sort(lst, new MyComparator());
        Iterator<Map.Entry> iter = lst.iterator();
        StringBuilder sb = new StringBuilder();
        while (iter.hasNext()) {
            Map.Entry entry = iter.next();
            for (int j=0; j<(int)entry.getValue(); j++) {
                sb.append(entry.getKey());
            }
        }
        return sb.toString();
    }
}