It's the Xinrui Ma

Blog

Top K Frequent Elements

Posted by in LeetCode on

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.

Solution: (key idea, sort the hashtable)
1. create a hashtable, key is the number in array, value is how many times they appear in the array.
2. create an array based on the hashtable, sort the array based on the value
3. slice the array to k size
4. generate the result array