[LeetCode] Top K Frequent Elements

jkyin 发布于2019-08-14 15:45 / 2824人阅读

Problem

Given a non-empty array of integers, return the k most frequent elements.

Example

Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note

You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm"s time complexity must be better than O(n log n), where n is the array"s size.

Solution

public class Solution {
    public List topKFrequent(int[] nums, int k) {
        int n = nums.length;
        Map map = new HashMap<>();
        for (int num: nums) {
            if (map.containsKey(num)) map.put(num, map.get(num)+1);
            else map.put(num, 1);
        }
        List[] freq = new ArrayList[n+1];
        for (int num : map.keySet()) {
            int i = map.get(num);
            if (freq[i] == null) {
                freq[i] = new ArrayList<>();
            }
            freq[i].add(num);
        }
        List res = new ArrayList<>();
        for (int index = freq.length - 1; index >= 0 && res.size() < k; index--) {
            if (freq[index] != null) {
                res.addAll(freq[index]);
            }
        }
        return res;
    }
}

Update 2018-9 PriorityQueue

class Solution {
    public List topKFrequent(int[] nums, int k) {
        List res = new ArrayList<>();
        if (nums == null || nums.length < k) return res;
        Map map = new HashMap<>();
        PriorityQueue> queue = new PriorityQueue<>((a, b)->b.getValue()-a.getValue());
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        for (Map.Entry entry: map.entrySet()) {
            queue.offer(entry);
        }
        int count = 0;
        while (count < k) {
            Map.Entry entry = queue.poll();
            res.add(entry.getKey());
            count++;
        }
        return res;
    }
}

Bucket sort

class Solution {
    public List topKFrequent(int[] nums, int k) {
        List res = new ArrayList<>();
        if (nums == null || nums.length < k) return res;
        Map map = new HashMap<>();
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        List[] buckets = new ArrayList[nums.length+1];
        for (Map.Entry entry: map.entrySet()) {
            int value = entry.getValue();
            if (buckets[value] == null) buckets[value] = new ArrayList<>();
            buckets[value].add(entry.getKey());
        }
        for (int i = buckets.length-1; i >= 0 && res.size() < k; i--) {
            if (buckets[i] != null) res.addAll(buckets[i]);
        }
        return res;
    }
}

云服务器 GPU云服务器 Frequent Elements LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65995.html

LeetCode 347. Top K Frequent Elements

摘要：描述给定一个非空的整数数组，返回其中出现频率前高的元素。然后以元素出现的次数为值，统计该次数下出现的所有的元素。从最大次数遍历到次，若该次数下有元素出现，提取该次数下的所有元素到结果数组中，知道提取到个元素为止。 Description Given a non-empty array of integers, return the k most frequent elements. E...

elva 2019-07-31 10:16 评论0 收藏0
leetcode347. Top K Frequent Elements

摘要：题目要求假设有一个非空的整数数组，从中获得前个出现频率最多的数字。先用来统计出现次数，然后将其丢到对应的桶中，最后从最高的桶开始向低的桶逐个遍历，取出前个频率的数字。题目要求 Given a non-empty array of integers, return the k most frequent elements. For example, Given [1,1,1,2,2,...

imccl 2019-08-15 15:54 评论0 收藏0
[LeetCode] Top K Frequent Elements [HashMap/Heap/T

摘要：先按照元素次数的将所有元素存入，再按照次数元素将哈希表里的所有元素存入，然后取最后的个元素返回。 Problem Given a non-empty array of integers, return the k most frequent elements. For example,Given [1,1,1,2,2,3] and k = 2, return [1,2]. Note: ...

AaronYuan 2019-08-14 15:56 评论0 收藏0
[LeetCode/LintCode] Top K Frequent Words

LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

0x584a 2019-08-15 13:32 评论0 收藏0
程序员进阶之算法练习：LeetCode专场

摘要：例如题目解析题目的意思很明显，就是把两个数字加起来，需要考虑进位的情况。总结这个题目如果都能独立完成，那么水平已经可以足以应付国内各大企业的算法面。欢迎大家前往腾讯云+社区，获取更多腾讯海量技术实践干货哦~ 本文由落影发表前言 LeetCode上的题目是大公司面试常见的算法题，今天的目标是拿下5道算法题：题目1是基于链表的大数加法，既考察基本数据结构的了解，又考察在处理加法过程中...

MrZONT 2019-08-23 13:42 评论0 收藏0