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

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

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

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個(gè)元素返回。

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;
    }
}