leetcode 451. Sort Characters By Frequency

╰+哭是因爲堅強的太久メ 2023-07-07 08:20 2阅读 0赞

**目录**

一、问题描述

二、代码实现

1、堆

2、桶排序

--------------------

[https://leetcode.com/problems/sort-characters-by-frequency/][https_leetcode.com_problems_sort-characters-by-frequency]

基于出现频率对字符串进行降序排序后返回。

## 一、问题描述 ##

测试用例：

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.

只需要按照出现频率排序即可，不需要参考字符的字典序。

## 二、代码实现 ##

### 1、堆 ###

class Solution {
        
        //堆
        public String frequencySort1(String s) {
            //计数 O(n)
            HashMap<Character, Integer> map = new HashMap<>();
            //for (char ch : s) {
            //error:for-each not applicable to expression type  required:array or java.lang.Iterable    found:String
            for (int i=0; i<s.length(); i++) {
                Character ch = s.charAt(i);
                map.put(ch, map.getOrDefault(ch, 0)+1);
            }
            
            //建立大顶堆 O(nlogm) m为不同字母的个数，m<=n（实际上m为256，所以其实这里是O(n)）
            // PriorityQueue<Character> heap = new PriorityQueue<>(
            //     (a, b) -> map.get(a).equals(map.get(b)) ? a.compareTo(b) : map.get(b).compareTo(map.get(a))
            // );
            PriorityQueue<Character> heap = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));
            // for (Character ch : map.keySet()) {
            //     heap.offer(ch);
            // }
            heap.addAll(map.keySet());
             
            //依次弹出堆顶元素并维护堆 O(nlogm)
            StringBuilder sb = new StringBuilder();
            while (!heap.isEmpty()) {
                Character ch = heap.poll();
                for (int i=0; i<map.get(ch); i++) {
                    sb.append(ch);
                }
            }
            
            return sb.toString();
        }
    }

### 2、桶排序 ###

class Solution {
        
        //桶排序（这种写法更快）
        public String frequencySort3(String s) {
            if (s == null || s.length() <= 1) {
                return s;
            }
            
            //计数  letters <-> frequencies
            int[] count = new int[256]; //由于题目没有要求整个Unicode编码，128不行
            int maxFrequency = Integer.MIN_VALUE;
            for (int i=0; i<s.length(); i++) {
                char ch = s.charAt(i);
                count[ch]++;
                maxFrequency = Math.max(maxFrequency, count[ch]);
            }
            
            //创建桶  frequencies <-> letters    如果这里用数组还可以再快
            HashMap<Integer, ArrayList<Character>> bucket = new HashMap<>();
            for (int i=0; i<256; i++) {
                if (count[i] != 0) {
                    int frequency = count[i];
                    if (!bucket.containsKey(frequency)) {
                        bucket.put(frequency, new ArrayList<Character>());
                    }
                    bucket.get(frequency).add((char)i);
                }
            }
            
            //从后往前遍历各个频率桶
            StringBuilder sb = new StringBuilder();
            for (int freq=maxFrequency; freq>=1; freq--) {
                if (bucket.get(freq) != null) {
                    ArrayList<Character> list = bucket.get(freq);
                    for (int i=0; i<list.size(); i++) {
                        Character ch = list.get(i);
                        for (int j=0; j<freq; j++) {
                            sb.append(ch);
                        }
                    }
                }
            }
            
            return sb.toString();
        }
        
        
        //桶排序
        public String frequencySort2(String s) {
            if (s == null || s.length() <= 1) {
                return s;
            }
            
            //计数 O(n)
            HashMap<Character, Integer> map = new HashMap<>();
            int max = Integer.MIN_VALUE;
            for (int i=0; i<s.length(); i++) {
                Character ch = s.charAt(i);
                int count = map.getOrDefault(ch, 0) + 1;
                map.put(ch, count);
                max = Math.max(max, count);
            }
            
            //创建桶 O(m)
            //ArrayList<Character>[] bucket = new ArrayList<>[max+1];
            //cannot create array with '<>'
            ArrayList<Character>[] bucket = new ArrayList[max+1];
            for (Character key : map.keySet()) {
                int frequency = map.get(key);
                if (bucket[frequency] == null) {
                    bucket[frequency] = new ArrayList<>();
                }
                bucket[frequency].add(key);
            }
            
            //从后往前遍历各个频率桶
            StringBuilder sb = new StringBuilder();
            for (int i=max; i>=1; i--) {
                if (bucket[i] != null) {
                    for (int j=0; j<bucket[i].size(); j++) {
                        Character ch = bucket[i].get(j);
                        for (int k=0; k<map.get(ch); k++) {
                            sb.append(ch);
                        }
                    }
                }
            }
            
            return sb.toString();
        }
    }

参考：

[https://leetcode.com/problems/sort-characters-by-frequency/discuss/93521/Super-simple-O(n)-Bucket-Sort-based-Java-solution-(11-ms).-No-fancy-Data-structure-needed.-Beats-96.][https_leetcode.com_problems_sort-characters-by-frequency_discuss_93521_Super-simple-O_n_-Bucket-Sort-based-Java-solution-_11-ms_.-No-fancy-Data-structure-needed.-Beats-96.]

[https_leetcode.com_problems_sort-characters-by-frequency]: https://leetcode.com/problems/sort-characters-by-frequency/
[https_leetcode.com_problems_sort-characters-by-frequency_discuss_93521_Super-simple-O_n_-Bucket-Sort-based-Java-solution-_11-ms_.-No-fancy-Data-structure-needed.-Beats-96.]: https://leetcode.com/problems/sort-characters-by-frequency/discuss/93521/Super-simple-O%28n%29-Bucket-Sort-based-Java-solution-%2811-ms%29.-No-fancy-Data-structure-needed.-Beats-96.