LeetCode | 0347.トップKの頻繁な要素[Python]

Leetcode 0347 Top K Frequent Elements

LeetCode0347。トップKの頻繁な要素[中] [Python] [バケットソート]

問題

LeetCode



空でない整数の配列が与えられた場合、 最も頻繁な要素。

例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. 最初に要素の頻度を数え、同じ要素の出現数を+1します。
  2. 次に、バケットソートを実行し、出現頻度に従って配列内の要素をグループ化します。つまり、頻度がiの要素がi番目のバケットに存在します。
  3. 最後に、最初の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)

コードアドレス

GitHubリンク