347. Top K Frequent Elements

Medium (Trung bình) Python 🔗 Xem trên LeetCode

📋 Đề Bài

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.

🧠 Thuật Toán & Kỹ Thuật

Hash Table (Bảng băm)Sorting (Sắp xếp)
⏱️ Thời gian O(n log n)
💾 Không gian O(n)

💻 Lời Giải

Python 0347-top-k-frequent-elements.py 
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = defaultdict(int)
        
        for num in nums:
            freq[num] += 1
            
        freq = dict(sorted(freq.items(), key = lambda x: x[1], reverse = True))
                
        return list(freq.keys())[:k]