LeetCode_451. 根据字符出现频率排序(优先队列(大顶堆)/哈希表)

107 阅读 0 评论 71 点赞

我是靠谱客的博主清新项链，最近开发中收集的这篇文章主要介绍LeetCode_451. 根据字符出现频率排序(优先队列(大顶堆)/哈希表)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在这里插入图片描述

思路

首先将字符和其对应的出现次数存入一个哈希表中，形成映射关系；
然后我们创建一个优先队列，存储的元素就是哈希表中的键值对，我们根据值(出现次数)，由大到小排列，(实现原理就是大顶堆)；
遍历哈希表的元素，将元素放入优先队列中，放入的过程中队列会自动根据出现次数由大到小将元素存入；
题目中要求倒序遍历出该字符串，所以我们使用 StringBuilder 来存储这个结果字符串；遍历这个优先队列，然后根据获取到的次数，将该字符添加到 StringBuilder 中；最后转换为字符串返回即可

代码实现(java)

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();

        char[] chars = s.toCharArray();

        for (char aChar : chars) {
            map.put(aChar, map.getOrDefault(aChar, 0) + 1);
        }

        final Set<Map.Entry<Character, Integer>> entries = map.entrySet();
        PriorityQueue<Map.Entry<Character, Integer>> queue = new PriorityQueue<>((o1, o2) -> o2.getValue() - o1.getValue());

        for (Map.Entry<Character, Integer> entry : entries) {
            queue.add(entry);
        }

        int len = queue.size();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) {
            Map.Entry<Character, Integer> poll = queue.poll();
            char c = poll.getKey();
            Integer value = poll.getValue();

            for (Integer integer = 0; integer < value; integer++) {
                sb.append(c);
            }
        }

        return sb.toString();
    }
}