9. Top K Frequent Elements

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

いきなりheapに飛びつくのはいただけない！

1 リストをソート

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        values_to_frequency = {}
        for num in nums:
            values_to_frequency[num] = values_to_frequency.get(num, 0) + 1
        
        frequent_values = []
        for value, frequency in values_to_frequency.items():
            frequent_values.append((value, frequency))
        frequent_values.sort(reverse=True, key=lambda value_frequency: value_frequency[1])

        if k < len(frequent_values):
            frequent_values = frequent_values[:k]
        
        return [value for value, _ in frequent_values]

2 heap

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        values_to_frequency = {}
        for num in nums:
            values_to_frequency[num] = values_to_frequency.get(num, 0) + 1
        
        frequent_values = []  #heap
        for value, frequency in values_to_frequency.items():
            heapq.heappush(frequent_values, (frequency, value))
            while k < len(frequent_values):
                heapq.heappop(frequent_values)
        
        return [value for _, value in frequent_values]

飛びついてもいいんだが、あなたこれどう解きますかと聞かれてheapしか出てこなかったら怖いなと思う。

3 bucket

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        values_to_frequency = {}
        for num in nums:
            values_to_frequency[num] = values_to_frequency.get(num, 0) + 1
        
        max_frequency = 10**5
        frequency_bucket = [[] for _ in range(max_frequency+1)]  #bucket frequency_bucket[v]: values which appear v times
        for value, frequency in values_to_frequency.items():
            frequency_bucket[frequency].append(value)
        
        top_k_values = []
        for i in range(len(frequency_bucket)-1,  -1, -1):
            top_k_values.extend(frequency_bucket[i])
            if len(top_k_values) >= k:
                break
        
        return top_k_values

使用メモリーが無駄にでかい。
マジックナンバーは使いたくないから変数初期化しとく。あと、変数の命名にデータ構造の名前入れるのってどうなんですかね？僕はあんまり好きじゃないんですが。

4 Quick Select

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        def quick_select(left, right):
            pivot_index = random.randint(left, right)
            pivot = values[pivot_index]
            pivot_frequency = values_to_frequency[pivot]
            values[pivot_index], values[right] = values[right], values[pivot_index]

            partition_index = left
            for i in range(left, right):
                if values_to_frequency[values[i]] > pivot_frequency:
                    values[i], values[partition_index] = values[partition_index], values[i]
                    partition_index += 1
            values[partition_index], values[right] = values[right], values[partition_index]

            if partition_index == k - 1:
                return None
            elif partition_index > k - 1:
                return quick_select(left, partition_index - 1)
            elif partition_index < k - 1:
                return quick_select(partition_index + 1, right)
        
        values_to_frequency = {}
        for num in nums:
            values_to_frequency.setdefault(num, 0)
            values_to_frequency[num] += 1

        values = list(values_to_frequency.keys())
        
        quick_select(0, len(values) - 1)

        return values[:k]

平均時間計算量: O(n) 最悪計算量: O(n^2) 空間計算量: O(1)
まぁコールスタックがかかりますが。制約条件からしてスタックオーバーフローしそうな匂いもしましたが、末尾最適化を信じます。
あと、sortの方が早いらしいです。開発者が無駄な処理をしないようにチューニングしてくれていて、かつネイティブコードで動作するからです。