347. 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,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.
 public class Solution { public List<Integer> topKFrequent(int[] nums, int k) { HashMap<Integer, Integer> map = new HashMap<>(); for (int num : nums) { if (!map.containsKey(num)) { map.put(num, 1); } else { map.put(num, map.get(num) + 1); } } List<Integer>[] bucket = new List[nums.length + 1]; for (int key : map.keySet()) { if (bucket[map.get(key)] == null) { bucket[map.get(key)] = new ArrayList<>(); } bucket[map.get(key)].add(key); } List<Integer> result = new ArrayList<>(); for (int i = bucket.length - 1; i >= 0; i--) { if (result.size() >= k) { return result; } if (bucket[i] != null) { result.addAll(bucket[i]); } } return result; } } 
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s