专栏首页后端CoderLeetCode72|前K个高频元素

LeetCode72|前K个高频元素

1,问题简述

给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

2,示例

示例 1:

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

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

提示:

你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

3,题解思路

优先级队列的使用,也就是堆

4,题解程序

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class TopKFrequentTest2 {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        int[] topKFrequent = topKFrequent(nums, k);
        for (int num : topKFrequent
        ) {
            System.out.print(num + "\t");
        }
    }

    public static int[] topKFrequent(int[] nums, int k) {
        if (nums == null || nums.length == 0 || nums.length < k) {
            return new int[k];
        }
        PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>(k, (o1, o2) -> o2.getValue().compareTo(o1.getValue()));
        HashMap<Integer, Integer> hashMap = new HashMap<>(nums.length);
        for (int num : nums
        ) {
            hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()
        ) {
            priorityQueue.offer(entry);
        }
        int[] array = new int[k];
        for (int i = 0; i < k; i++) {
            array[i] = priorityQueue.poll().getKey();
        }
        return array;
    }
}

5,题解程序图片版

6,总结

hashMap键值对集合加上堆排序的使用,也算是堆,即优先级队列的使用吧,一般自己的写法都是很常规的写法,所以看懂java语法就知道怎么个意思了。

本文分享自微信公众号 - WwpwW(gh_245290c1861a),作者:后端Coder

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode45|数组中重复的数据

    给定一个整数数组 a,其中1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。

    码农王同学
  • LeetCode10|只出现一次的数字II

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

    码农王同学
  • LeetCode32|前k个高频元素

    6,键值对集合的使用,这里自己也曾经分析过java集合的源码,具体见下面的链接吧,但是自己从未去写过hashMap的源码,因为网络上这样的文章的太多了,自己倒是...

    码农王同学
  • C++版 - Leetcode No.1 - Two sum题解

    提交网址: https://leetcode.com/problems/two-sum/

    Enjoy233
  • LeetCode45|数组中重复的数据

    给定一个整数数组 a,其中1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。

    码农王同学
  • Leetcode 268. Missing Number

    Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find ...

    triplebee
  • No.015 3Sum

    15. 3Sum Total Accepted: 131800 Total Submissions: 675028 Difficulty: Medium   G...

    mukekeheart
  • LeetCode32|前k个高频元素

    6,键值对集合的使用,这里自己也曾经分析过java集合的源码,具体见下面的链接吧,但是自己从未去写过hashMap的源码,因为网络上这样的文章的太多了,自己倒是...

    码农王同学
  • LintCode-761. 最小子集

    给一非负整数数组. 取数组中的一部分元素, 使得它们的和大于数组中其余元素的和, 求出满足条件的元素数量最小值.

    悠扬前奏
  • LeetCode10|只出现一次的数字II

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

    码农王同学

扫码关注云+社区

领取腾讯云代金券