0top-k-frequent-elements

Try it on leetcode

Description

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

 

Example 1:

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

Example 2:

Input: nums = [1], k = 1
Output: [1]

 

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

 

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Solution(Python)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return self.bucketsort(nums, k)
    
    # Time Complexity: O(nlogn)    
    def naive(self, nums: List[int], k: int) -> List[int]:
        freqmap = Counter(nums)
        sorted_freq = sorted(freqmap.keys(),key=freqmap.get,reverse=True)
        return sorted_freq[:k]
    
    # Time Complexity: O(nlogk)   
    def better(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        
        if k == n:
            return nums
        freq_map = Counter(nums)
        return heapq.nlargest(k, freq_map.keys(),key=freq_map.get)
    
    # Time Complexity: O(n)  
    def bucketsort(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        buckets = [[] for _ in range(n+1)]
        freq_map = Counter(nums)
        
        for num in freq_map:
            buckets[freq_map[num]].append(num)
            
        buckets = [val for bucket in buckets for val in bucket]
        return buckets[-k:]