使用哈希表+优先队列解决字符频率问题

137 阅读 0 评论 91 点赞

我是靠谱客的博主鲤鱼白猫，最近开发中收集的这篇文章主要介绍使用哈希表+优先队列解决字符频率问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在求解算法题时，往往我们遇见的不是纯算法的题目，而是参杂着数据结构的题型；例如一般我们遇到需要统计字符出现的次数时，往往使用哈希表来记录数量，但是我们要找到最大的出现频率的元素，往往很难直接通过哈希表的来获取相应的value值，此时往往可以通过构造优先队列的方式来取值。
接下来将列举几道有关使用哈希表+优先队列求解出现频率的类型题，望大家参考：

题目1概述：前K个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。

示例：

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

算法思路：
这几道题目的算法思路基本相同，在这里不再一一论述，大致思想是通过HashMap先记录某种元素出现的次数，然后通过定义数组来将<key,value>构造成相应元素，通过优先队列进行排序，这里要注意构造优先队列的构造方法中要设置元素大的在根结点中；（这里下一题和这题不同的思路是，下一题的元素是字符型，那么我们可以将出现的次数这个整型变量转化成字符串类型，然后在定义优先队列的时候再转成int类型做差即可）

算法实现：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //定义集合来计算某个元素出现的频率
        Map<Integer,Integer> hash = new HashMap<>();
        //定义优先队列用来找出前k大元素
        //每个元素的第二个元素比较大小
        PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)->b[1]-a[1]);
        for(int i=0;i<nums.length;i++){
            if(!hash.containsKey(nums[i])){
                hash.put(nums[i],1);
            }else{
                hash.put(nums[i],hash.get(nums[i])+1);
            }
        }
        for(int num:hash.keySet()){
            int[] arr = {num,hash.get(num)};
            //将数组加入到优先队列当中
            queue.offer(arr);
        }
        //定义一个变量用来存储结果
        int[] res = new int[k];
        for(int i=0;i<k;i++){
            //取出元素
            res[i] = queue.poll()[0];
        }
        return res;
    }
}

题目2概述：根据字符出现频率排序
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

示例：

输入:
"tree"
输出:
"eert"
解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

输入:
"cccaaa"
输出:
"cccaaa"
解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

算法实现：

class Solution {
    public String frequencySort(String s) {
        Map<String,String> hash = new HashMap<>();
        for(int i=0;i<s.length();i++){
            String str = s.substring(i,i+1);
            if(!hash.containsKey(str)){
                hash.put(str,String.valueOf(1));
            }else{
                hash.put(str,String.valueOf(Integer.parseInt(hash.get(str))+1));
            }
        }
        //定义一个优先队列
        PriorityQueue<String[]> queue = new PriorityQueue<>((a,b)->Integer.parseInt(b[1])-Integer.parseInt(a[1]));
        //将每个元素构造成数组形式
        for(String st:hash.keySet()){
            String[] arr = {st,hash.get(st)};
            queue.offer(arr);
        }
        String rs = "";
        while(!queue.isEmpty()){
            //当优先队列当中的元素不为空
            String[] num = queue.poll();
            for(int i=0;i<Integer.parseInt(num[1]);i++){
                //按照元素出现的次数拼接起来
                rs+=num[0];
            }
        }
        return rs;
    }
}