Leetcode 347 Top K Frequent Elements

Soru

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

Örnek 1

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

Örnek 2

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

Çözüm

  • First we need count the appearence for each element store it in dictionary. Then we iterate the dictionary, and push the value-key pair (or count-value pair) into heap, if the the heap length less than k. When heap length is greater or equal than k, we push the current value-key pair into heap and pop one from the heap in order to keep the length of the heap equal to key. After iteration, we will get the k most frequent elements pair, we only need to return the value not the count.

Code

class Solution:
    def topKFrequent(nums, k):
        # Elemanların frekansını hesapla
        count = Counter(nums)
        # En sık kullanılan k elemanı bulmak için min-heap kullan
        # Heap içinde (frekans, eleman) tuple'ları sakla
        heap = []
        for num, freq in count.items():
            heapq.heappush(heap, (-freq, num))
        
        # Heap'ten en sık kullanılan k elemanı çıkar
        return [heapq.heappop(heap)[1] for _ in range(k)][::-1]
        
        
        
        

Complexity