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日

相关推荐

  • leetcode27-移除元素

    原题 给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(…

    算法 2019年11月20日
    070
  • leetcode67-二进制求和

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

    算法 2019年11月15日
    090
  • leetcode41-缺失的第一个正数

    原题 给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3…

    算法 2020年5月11日
    0120
  • 'leetcode50-Pow(x,n)'

    原题 实现 pow(x, n) ,即计算 x 的 n 次幂函数。 示例1: 输入: 2.00000, 10 输出: 1024.00000 示例2: 输入: 2.10000, 3 输…

    算法 2020年1月5日
    0160
  • leetcode705-设计哈希集合

    原题 不使用任何内建的哈希表库设计一个哈希集合 具体地说,你的设计应该包含以下的功能 add(value):向哈希集合中插入一个值。 contains(value) :返回哈希集合…

    算法 2019年12月18日
    0140
  • leetcode945-使数组唯一的最小增量

    原题 给定整数数组 A,每次 move 操作将会选择任意 A[i],并将其递增 1。 返回使 A 中的每个值都是唯一的最少操作次数。 示例 1: 输入: [1,2,2] 输出: 1…

    算法 2020年3月22日
    0630
  • leetcode33-搜索旋转排序数组

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值,…

    算法 2020年1月1日
    0150
  • leetcode999-车的可用捕获量

    原题 999. 车的可用捕获量 - 力扣(LeetCode) 解法 思想 这道题题目有点难理解,其实就是上下左右搜索,质量有点低了。 代码 class Solution { cha…

    算法 2020年3月26日
    070
  • leetcode76-最小覆盖子串

    原题 给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。 示例: 输入: S = "ADOBECODEBANC", T = "ABC" 输…

    算法 2020年5月23日
    0150
  • leetcode1103-分糖果II

    原题 排排坐,分糖果。 我们买了一些糖果 candies,打算把它们分给排好队的 n = num_people 个小朋友。 给第一个小朋友 1 颗糖果,第二个小朋友 2 颗,依此类…

    算法 2020年3月5日
    0130

发表回复

登录后才能评论