NeetCodeのSolutionを書いていく

#

Top K Frequent Elements

#

問題概要

#

整数の配列numsと整数kが与えられます。 最も出現回数の多いkこの配列を返しなさい。 答えは常にユニークになっていて順番は問いません。

例

#

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

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

計算量：O(n) メモリ：O(n) を狙う

メモ

#

答えはユニークになるので、上記k番が2つ以上あるケースはない。 numsの要素でループしてdictに詰めてvalueでsortして上位k個のkeyを返す？

通っちゃったけど、以下の前提が満たせていない気がする。

-1000 <= nums[i] <= 1000

numsに負の値が入るとだめ。でも回答もここをケアしていない。

from collections import defaultdict
from typing import List


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        values: dict[int, int] = defaultdict(int)
        for i in nums:
            values[i] += 1
        values_sorted = sorted(values.items(), key=lambda x: x[1], reverse=True)
        return [key for key, value in values_sorted[:k]]