303. Top K Frequent Elements
Medium
Frequency Map and Buckets
Hashing
Problem
Given an integer array nums and an integer k, return the k most frequent distinct elements. The answer may be returned in any order.
Examples
Example 1
Input: [1,1,1,2,2,3], 2
Output: [1,2]
Example 2
Input: [1], 1
Output: [1]
Example 3
Input: [4,4,4,5,5,6], 1
Output: [4]
Constraints
� 1 <= nums.length <= 100000
� k is between 1 and the number of distinct elements.
� The answer is guaranteed to be unique.
Hints
?? First count the frequency of each distinct value.
?? A heap can maintain the best k values.
?? Because frequency cannot exceed nums.length, bucket sorting can achieve linear time.
Expected Complexity
Time: O(n)
Space: O(n)
Follow-up
Can you solve it in O(n) time using frequency buckets?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
[1,1,1,2,2,3], 2Expected
[1,2]