LeetCode | 0347.トップKの頻繁な要素[Python]
Leetcode 0347 Top K Frequent Elements
LeetCode0347。トップKの頻繁な要素[中] [Python] [バケットソート]
問題
空でない整数の配列が与えられた場合、 に 最も頻繁な要素。
例1：
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] 例2：
Input: nums = [1], k = 1 Output: [1] 注意：
- あなたは仮定するかもしれません に 常に有効、1≤ に ≤一意の要素の数。
- アルゴリズムの時間計算量 でなければなりません O（ n ログ n ）、 どこ n は配列のサイズです。
問題
空でない整数配列が与えられた場合、前の頻度を返します に 高元素。
例1：
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] 例2：
Input: nums = [1], k = 1 Output: [1] 説明：
- 与えられたkは常に妥当であり、1≤k≤配列内の異なる要素の数であると想定できます。
- アルゴリズムの時間計算量 する必要がある O（ n log n ）、 n 配列のサイズです。
アイデア
バケットソート
- 最初に要素の頻度を数え、同じ要素の出現数を+1します。
- 次に、バケットソートを実行し、出現頻度に従って配列内の要素をグループ化します。つまり、頻度がiの要素がi番目のバケットに存在します。
- 最後に、最初のk個の要素がバケットから逆の順序で取得されます。
時間の複雑さ ： オン）
スペースの複雑さ ： オン）
Pythonコード
class Solution(object): def topKFrequent(self, nums, k): ''' :type nums: List[int] :type k: int :rtype: List[int] ''' # Frequency of statistical elements count = dict() for num in nums: count[num] = count.get(num, 0) + 1 # Return the value corresponding to the num element in the dictionary count, if not, assign the value to 0 # Bucket sort bucket = [[] for i in range(len(nums) + 1)] for key, value in count.items(): bucket[value].append(key) # Take out the first k elements in reverse order res = list() for i in range(len(nums), -1, -1): # The last -1 means reverse order if bucket[i]: res.extend(bucket[i]) # Append elements to the end of the list if len(res) >= k: # Only the first k break return res[:k] # Output the element before the kth (including the kth element)