[LeetCode] Top K Frequent Elements [HashMap/Heap/T

AaronYuan 发布于2019-08-14 15:56 / 1053人阅读

摘要：先按照元素次数的将所有元素存入，再按照次数元素将哈希表里的所有元素存入，然后取最后的个元素返回。

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:
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.

Note Solution TreeMap

Store each nums element and its count in HashMap.

Traverse its keySet(), store the count of each key into TreeMap, which means reverse the key-value pairs. And TreeMap will sort the elements by count value.

Use pollLastEntry() to get last K entries from TreeMap; then addAll() to put values in ArrayList res.

先按照元素-次数的pair将所有元素存入HashMap，再按照次数-元素pair将哈希表里的所有元素存入TreeMap，然后取TreeMap最后的k个元素返回。

public class Solution {
    public List topKFrequent(int[] nums, int k) {
        Map map = new HashMap<>();
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        TreeMap> sorted = new TreeMap<>();
        for (int num: map.keySet()) {
            int count = map.get(num);
            if (!sorted.containsKey(count)) sorted.put(count, new LinkedList<>());
            sorted.get(count).add(num);
        }
        List res = new ArrayList<>();
        while (res.size() < k) {
            Map.Entry> entry = sorted.pollLastEntry();
            res.addAll(entry.getValue());
        }
        return res;
    }
}

Min Heap lambda-expression

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

no-lambda

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

Max Heap

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

私有云服务器托管 Frequent Elements LeetCode LeetCode_String

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

转载请注明本文地址：https://www.ucloud.cn/yun/66124.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

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 e...

jkyin 2019-08-14 15:45 评论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