NeetCode 150 [Arrays & Hashing]:medium 2/6

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]]