347.Top-K-Frequent-Elements

347. Top K Frequent Elements

题目地址

https://leetcode.com/problems/top-k-frequent-elements/

题目描述

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

Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:
Input: nums = [1], k = 1
Output: [1]
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.

代码

Approach 1: Heap

Complexity Analysis

• Time complexity : O(N_log(_k)). The complexity of `Counter method is O(N). To build a heap and output list takes O(N_log(_k)). Hence the overall complexity of the algorithm is O(N+N_log(_k)=O(N_log(_k).

• Space complexity : O(N) to store the hash map.

class Solution {
  public List<Integer> topKFrequent(int[] nums, int k) {
    HashMap<Integer, Integer> count = new HashMap();
    for (int n : nums) {
      count.put(n, count.getOrDefault(n, 0) + 1);
    }

    PriorityQueue<Integer> heap = new PriorityQueue<Integer>((n1, n2) -> count.get(n1) - count.get(n2));

    for (int n : count.keySet()) {
      heap.add(n);
      if (heap.size() > k) 
        heap.poll();
    }

    List<Integer> ans = new LinkedList();
    while (!heap.isEmpty()) {
      ans.add(heap.poll());
    }
    Collections.reverse(ans);
    return ans;
    }
}