# LeetCode Medium 347. Top K Frequent Elements

tags: leetcode

問題

• Explore
• Problems

アイデア

空でない整数列が与えられた時，$k$個の最も頻繁に現れる整数を返せという問題です．

整数と登場回数を結びつけるようなデータ構造を使えばいいですね．

解法

• 連想配列を使ってkey=整数，value=登場回数とします．
• 登場回数で降順にソートし，先頭k個を返します．

計算量

numsの大きさを$N$とします．

• 時間計算量
  • $O(N \log N)$
• 空間計算量
  • $O(N)$

Python

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        num_occur = {}
        for num in nums:
            if num in num_occur:
                num_occur[num] += 1
            else:
                num_occur[num] = 1
                
        res = [key for key, value in sorted(num_occur.items(), key=lambda x: x[1], reverse=True)]
        return res[:k]