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

AaronYuan 發(fā)布于2019-08-14 15:56 / 1306人閱讀

摘要：先按照元素次數(shù)的將所有元素存入，再按照次數(shù)元素將哈希表里的所有元素存入，然后取最后的個元素返回。

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.

先按照元素-次數(shù)的pair將所有元素存入HashMap，再按照次數(shù)-元素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;
    }
}

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://www.ezyhdfw.cn/yun/66124.html

LeetCode 347. Top K Frequent Elements

摘要：描述給定一個非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前高的元素。然后以元素出現(xiàn)的次數(shù)為值，統(tǒng)計該次數(shù)下出現(xiàn)的所有的元素。從最大次數(shù)遍歷到次，若該次數(shù)下有元素出現(xiàn)，提取該次數(shù)下的所有元素到結果數(shù)組中，知道提取到個元素為止。 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

摘要：題目要求假設有一個非空的整數(shù)數(shù)組，從中獲得前個出現(xiàn)頻率最多的數(shù)字。先用來統(tǒng)計出現(xiàn)次數(shù)，然后將其丟到對應的桶中，最后從最高的桶開始向低的桶逐個遍歷，取出前個頻率的數(shù)字。題目要求 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專場

摘要：例如題目解析題目的意思很明顯，就是把兩個數(shù)字加起來，需要考慮進位的情況?？偨Y這個題目如果都能獨立完成，那么水平已經可以足以應付國內各大企業(yè)的算法面。歡迎大家前往騰訊云+社區(qū)，獲取更多騰訊海量技術實踐干貨哦~ 本文由落影發(fā)表前言 LeetCode上的題目是大公司面試常見的算法題，今天的目標是拿下5道算法題：題目1是基于鏈表的大數(shù)加法，既考察基本數(shù)據(jù)結構的了解，又考察在處理加法過程中...

MrZONT 2019-08-23 13:42 評論0 收藏0