leetcode347-前K个高频元素

原题

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

示例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 是数组的大小。

解法

思想

可以用哈希表记录下出现的次数,然后将哈希表按值排序。(获取entryList用Collections来排序)

代码

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        for(int i:nums){
            map.put(i,map.getOrDefault(i,0)+1);
        }
        List<Map.Entry<Integer,Integer>> entryList = new ArrayList<>(map.entrySet());
        entryList.sort((entry1, entry2) -> entry2.getValue() - entry1.getValue());
        int n = 0;
        for(Map.Entry<Integer,Integer> i:entryList){
            if(n>=k) break;
            list.add(i.getKey());
            n ++;
        }
        return list;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode347-%e5%89%8dk%e4%b8%aa%e9%ab%98%e9%a2%91%e5%85%83%e7%b4%a0/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月27日
下一篇 2019年12月28日

相关推荐

  • leetcode1371-每个元音包含偶数次的最长子字符串

    原题 给你一个字符串 s ,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 'a','e','i','o','u' ,在子字符串中都恰好出现了偶数次。 示例 1: 输入…

    算法 2020年5月20日
    01560
  • leetcode67-二进制求和

    原题 给定两个二进制字符串,返回他们的和(用二进制表示)。 输入为非空字符串且只包含数字 1 和 0。 示例 1: 输入: a = “11”, b = “1” 输出: “100” …

    算法 2019年11月15日
    0100
  • leetcode124-二叉树中的最大路径和

    原题 给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 示例 1: 输入: [1…

    算法 2020年4月26日
    0170
  • 剑指offer45-把数组排成最小的数

    原题(来源Leetcode) 输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: "102" …

    算法 2020年6月11日
    0150
  • leetcode599-两个列表的最小索引总和

    原题 假设Andy和Doris想在晚餐时选择一家餐厅,并且他们都有一个表示最喜爱餐厅的列表,每个餐厅的名字用字符串表示。 你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果…

    算法 2019年12月22日
    0120
  • leetcode1028-从先序遍历还原二叉树

    原题 我们从二叉树的根节点 root 开始进行深度优先搜索。 在遍历中的每个节点处,我们输出 D 条短划线(其中 D 是该节点的深度),然后输出该节点的值。(如果节点的深度为 D,…

    2020年6月18日
    02410
  • leetcode733-图像渲染

    原题 有一幅以二维整数数组表示的图画,每一个整数表示该图画的像素值大小,数值在 0 到 65535 之间。 给你一个坐标 (sr, sc) 表示图像渲染开始的像素值(行 ,列)和一…

    2019年12月13日
    0100
  • leetcode290-单词规律

    原题 https://leetcode.cn/problems/word-pattern/description/ 解法 类似leetcode205-同构字符串 func word…

    算法 2024年3月26日
    050
  • leetcode32-最长有效括号

    原题 给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。 示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2…

    算法 2020年6月12日
    0160
  • leetcode402-移掉K位数字

    原题 给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。 注意: num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。 …

    算法 2020年1月29日
    0100

发表回复

登录后才能评论