ゼロから始めるLeetCode Day81 「347. Top K Frequent Elements」
概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。
と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。
ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
Python3で解いています。
前回
ゼロから始めるLeetCode Day80「703. Kth Largest Element in a Stream」
次回
ゼロから始めるLeetCode Day82「392. Is Subsequence」
Twitterやってます。
問題
347. Top K Frequent Elements
難易度はMedium。
前回の問題同様Heapを使った問題です。
問題としては、数字が格納された空ではない配列が与えられます。その配列の中からK番目まで頻出の要素を返すようなアルゴリズムを設計してください、というものです。
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
解法
Counterを使ってリストの要素を調べ、keyを取得、そしてheapのnlargestを使って書きました。
import heapq
import collections
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = collections.Counter(nums)
key = count.get
return heapq.nlargest(k,count.keys(),key)
# Runtime: 108 ms, faster than 66.40% of Python3 online submissions for Top K Frequent Elements.
# Memory Usage: 18.2 MB, less than 79.07% of Python3 online submissions for Top K Frequent Elements.
なお、nlargestの引数はn, iterable, key=Noneという順番です。
では今回はここまで。
お疲れ様でした。
コメント
コメントを投稿