leetcode【栈与队列—中等】347.前 K 个高频元素

文章目录

• 前言
• 题目
• 题解
• NO1：哈希表+优先队列
• NO2：排序遍历+优先队列
• 参考文章

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为栈与队列专题。

---

题目

题目来源leetcode

leetcode地址：347. 前 K 个高频元素，难度：中等。

题目描述(摘自leetcode)：

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

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

示例 2:
输入: nums = [1], k = 1
输出: [1]
 
提示：
1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

本地调试代码：

class Solution {

    public int[] topKFrequent(int[] nums, int k) {
        ...
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,1,1,2,2,3};
        System.out.println(Arrays.toString(new Solution().topKFrequent(nums,2)));
    }

}

---

题解

NO1：哈希表+优先队列

思路： 先使用哈希表来进行统计对应值的频率，之后创建一个优先队列设置一个从小到大排序的比较器，每次插入一组key、value后，判断当前的容量是否>k个，若是大于了直接将队头的出队(在队列里频率最小的)，最终遍历取出队列中的k组数据即可。

代码：

public int[] topKFrequent(int[] nums, int k) {
    //使用map来进行统计指定指定数的频率，key为num，value为频率
    Map<Integer,Integer> map = new HashMap<>();
    for (int num : nums) {
        map.put(num,map.getOrDefault(num,0)+1);
    }
    Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
    //创建优先队列，传入Comparator匿名接口类，插入队列的元素从小到达排列
    PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1,o2)->o1.getValue()-o2.getValue());
    for (Map.Entry<Integer, Integer> entry : entries) {
        queue.offer(entry);
        if(queue.size() > k){  //一旦队列中的数量大于k，直接将频率最小的出队(队头)
            queue.poll();
        }
    }
    //最终取出对应的最大k值
    int[] maxNums = new int[k];
    for (int i = k-1; i >=0 ; i--) {
        maxNums[i] = queue.poll().getKey();
    }
    return maxNums;
}

---

NO2：排序遍历+优先队列

思路：首先进行从小到大排序，之后对整个数组进行遍历，以[i]!=[i-1]来作为存储到队列的依据，队列按照从大到小排序，每次入队后判断是否>k个，若是大于出队。最终遍历k个即可获取到前k个高频元素。

代码：

public int[] topKFrequent(int[] nums, int k) {
    Arrays.sort(nums);
    //优先队列，按照频率从小到大排列(Comparator返回值为负数就从小到大排列，若是正数从大到小)
    PriorityQueue<int[]> queue = new PriorityQueue<int[]>((o1, o2) -> o1[1] - o2[1]);
    //对数组进行遍历操作
    int i = 1;
    int j = 1;
    for (; i < nums.length; i++) {
        if (nums[i] == nums[i - 1]) {
            j++;
        } else {
            queue.offer(new int[]{nums[i - 1], j});
            if (queue.size() > k) {  //一旦大于原本k个数量就进行移除
                queue.poll();
            }
            j = 1;
        }
    }
    queue.offer(new int[]{nums[i - 1], j});
    if (queue.size() > k) {
        queue.poll();
    }
    //从队列中取出k个
    int[] maxNums = new int[k];
    for (int l = 0; l < k; l++) {
        maxNums[l] = queue.poll()[0];
    }
    return maxNums;
}

---

参考文章

[1]. leetcode题解

[2]. 代码随想录—347.前 K 个高频元素

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.11.4