Top K Frequent Elements
整数の配列 nums と整数 k が与えられます。nums に最も多く出現する順に、出現頻度の高い k 個の値を返してください。2つの値の出現回数が同じ場合は、小さい値を先にします。
各値は nums で何回出現しても、答えには1回だけ含めます。また、k が異なる値の個数を超えることはありません。
関数
- numsinteger-array
- カウントする値
- kinteger
- 返す値の数
- 戻り値integer-array
- 出現頻度が高い順に k 個の値を返し、頻度が同じ場合は値の小さい順に並べます。
制約
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ kであり、kはnums内の異なる値の数以下です。
例
- 入力
- nums = [4, 1, 4, 2, 1, 4, 3, 1, 4]k = 2
- 出力
- [4, 1]
- 説明
4は4回、1は3回、2と3はそれぞれ1回出現します。最も頻度の高い2つの値は、4、次に1です。
- 入力
- nums = [5, -2, 7, -2, 7, 5, 9]k = 2
- 出力
- [-2, 5]
- 説明
-2、5、7はそれぞれ2回、9は1回出現します。最も多く出現する値が3つあるため、そのうち小さい2つである-2と5が答えです。
- 入力
- nums = [8]k = 1
- 出力
- [8]
- 説明
- 値は1つなので、それが最頻値です。
提出時に隠しテスト+16件
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
まず、各値が何回出現するかを調べましょう。1回の走査で値とその出現回数を対応付けるデータ構造は何でしょうか？
カウントが分かったら、ある順序に基づいて最良の値を
k個求めます。カウントが多い値を先にし、同数の場合は値が小さい方を先にします。異なる値をすべてソートする方法もあります。サイズkの最小ヒープを使えば、答えに残る可能性のある値だけを保持できます。カウントとは、1から
nまでの整数です。カウントごとにバケットを1つ作り、バケットcにはc回出現する値を入れ、カウントの多い順にバケットを読み取ります。値を小さいものから大きいものへ順にたどってバケットを埋めれば、各バケット内はすでに同順位の順序になっています。
解説
数え上げは手早く済みます。ハッシュマップで1回走査すれば、各値の出現回数がわかります。本当に考えるべきなのは、必要以上に作業を増やさずに、最も優れた値をk個選ぶ方法です。異なるd個の値すべてを出現回数でソートするとO(d log d)かかりますが、サイズkの最小ヒープを使えばO(d log k)に抑えられます。また、出現回数は1からnまでの整数なので、バケットソートを使えば比較を一切行わずに、出現回数順に値を並べられます。
個数を数え、その個数順に並べ替える
考え方
まず数えます。値から個数へのハッシュマップを使って1回走査すると、[4, 1, 4, 2, 1, 4, 3, 1, 4]は4 → 4、1 → 3、2 → 1、3 → 1になります。
次に、異なる値を答えの順序に並べます。個数が多い順、個数が同じなら値が小さい順です。個数を第1キー、値を第2キーとして、まさにその比較でソートすれば、ソート済みリストの先頭k個が答えになります。ここでは順序は4, 1, 2, 3で、k = 2なら4と1が残ります。
数え上げの計算量はO(n)です。異なる値d個のソートにはO(d log d)かかり、すべての値が異なる場合でも最大でO(n log n)です。値が10^4個なら比較は約1.3 × 10^5回で、高速です。無駄なのは、必要なのが先頭k個だけなのに、すべての値をソートすることです。
アルゴリズム
- ハッシュマップ内の各値を数えます。
- 異なる値をリストに入れます。
- リストをカウントの多い順に並べ、カウントが同じ場合は値の小さい順に並べます。
- 先頭の
k個の値を返します。
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Most frequent first; equal counts put the smaller value first.
ordered = sorted(counts, key=lambda value: (-counts[value], value))
return ordered[:k]最良のk個を最小ヒープに保持する
考え方
必要なのは最良の値k個だけなので、候補もk個だけ保持します。新しい値ごとに、それが保持している最も弱い候補に勝るかどうかを判定します。ここで弱いとは、出現回数が少ない、または出現回数が同じで値が大きいことを意味します。このルールで順序付けた最小ヒープを使えば、最も弱い候補が先頭に来るため、O(1)で参照し、O(log k)で置き換えられます。
重複のない値を順に調べます。ヒープに含まれる値がk個未満の間は、その値を追加します。その後は、先頭の値を上回る値であれば置き換え、そうでなければ破棄します。すでにより優れた値がk個保持されているからです。ライブラリのヒープを使う場合は、すべての値をプッシュし、ヒープがk個を超えるたびに一度ポップするほうが簡潔で、同じk個の値を保持できます。
最後にヒープには答えが含まれていますが、答えの順には並んでいません。ヒープは部分的にしかソートされていないためです。ポップすると最も弱い値から返されるので、答えは最後の位置から最初の位置へ向かって書き込みます。
重複のないd個の値それぞれについて、k個の要素を持つヒープ操作が最大1回必要となるため、選択にかかる時間はO(d log k)です。これは、8000個の重複のない値から上位10個を選ぶ場合のように、kがdより大幅に小さいとき、ソートより高速です。
アルゴリズム
- ハッシュマップ内の各値を数えます。
- 異なる値ごとに、ヒープ内の値が
k個未満であれば、その値を追加します。 - ヒープが満杯になったら、その値をトップにある、保持している値の中で最も弱い値と比較します。新しい値のほうが強ければ、トップに置いて下方向にふるい落とします。
- ヒープから
k回ポップし、最後の位置から最初の位置に向かって、それぞれの値を答えに書き込みます。
import heapq
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Entries are (count, -value). heapq keeps the smallest entry on top, which is
# the weakest value kept: the lowest count, and on a tie the larger value.
heap = []
for value, count in counts.items():
heapq.heappush(heap, (count, -value))
if len(heap) > k:
heapq.heappop(heap)
# Pops come out weakest first, so fill the answer from the back.
result = [0] * k
for i in range(k - 1, -1, -1):
result[i] = -heapq.heappop(heap)[1]
return result数えてから、出現回数でバケットソートする
考え方
カウントはどんな数でもよいわけではありません。1 から n までの整数です。これによりバケットソートが使えます。カウントごとにバケットを1つ用意し、バケット c にはちょうど c 回出現する値を入れ、バケット n から順にバケットを読み取ります。値は出現頻度の高い順に取り出され、カウント同士を比較することはありません。
同順位のルールでは、もう1つ条件があります。バケット内では、小さい値を先に並べます。値は -10^4 から 10^4 までなので、R = 2 × 10^4 + 1 個のカウンターを持つ配列でカウントでき、値 v はインデックス v + 10^4 に格納できます。その配列を最小値から最大値まで順にたどり、各値をそのカウントに対応するバケットに追加します。各バケットは昇順に埋まるため、同順位の順序が保たれ、ソートは必要ありません。
[5, -2, 7, -2, 7, 5, 9] の場合、この走査によって -2、5、7 がこの順でバケット2に入り、9 がバケット1に入ります。バケット7から順に読み取ると、値が入っている最初のバケットはバケット2であり、k = 2 なら -2 と 5 が取り出されます。
処理は、nums を1回、R 個のカウンターを1回、バケットを1回走査するため、合計で O(n + R) です。値の範囲が固定なら線形時間です。カウント用配列の代わりにハッシュマップを使ってもカウントは線形時間のままですが、バケットはマップの順序で埋まるため、同順位のルールに従うには各バケットをソートする必要があります。
アルゴリズム
- 配列内の各値を、インデックス
value + 10^4に対応する位置で数えます。 - 1 から
nまでのバケットを作り、可能な出現回数ごとに1つのリストを用意します。 - カウント配列を最小値から最大値まで走査し、出現する各値をその出現回数に対応するバケットに追加します。
- 出現回数
nから1までバケットを読み取り、k個になるまで値を取り出します。
def topKFrequent(nums, k):
OFFSET = 10000 # values run from -10^4 to 10^4
counts = [0] * (2 * OFFSET + 1)
for x in nums:
counts[x + OFFSET] += 1
# buckets[c] lists the values that occur exactly c times. Walking the
# values from smallest to largest fills every bucket in ascending order.
buckets = [[] for _ in range(len(nums) + 1)]
for i, c in enumerate(counts):
if c > 0:
buckets[c].append(i - OFFSET)
# Read the buckets from the highest count down until k values are taken.
result = []
for c in range(len(nums), 0, -1):
for value in buckets[c]:
result.append(value)
if len(result) == k:
return result
return result
落とし穴と境界ケース
数え間違いはめったにありません。間違いやすいのは、答えの順序です。
- 同数の場合に、最初に現れた順やハッシュマップの順で決めてしまう。2つ目の例では、
-2、5、7はいずれも2回出現し、小さい値を優先するルールだけによって、[-2, 5]が唯一の正解になります。 - ヒープの配列をそのまま返してしまう。ヒープは部分的にしか順序付けられておらず、先頭にあるのは最も弱い値、つまり最後に来る値です。
- ヒープの同数時のルールを逆にしてしまう。同じ出現回数の2つの値では、大きい方が弱いため、
(count, value)による最小ヒープでは誤った値が取り除かれます。(count, -value)を使うか、このルールに合わせて比較処理を書きましょう。 - 異なる値の個数と同じ数だけバケットを作ってしまう。
[3, 3, 3, 3]のように、1つの値がn回出現することがあるため、バケットnが必要です。 - Javaで、2つの
Integerの出現回数を!=で比較してしまう。これは参照を比較するため、出現回数が127を超えると正しく動作しません。まずintにアンボックスしましょう。 - 最後にバケット全体を取得してしまう。バケットの途中であっても、
k個の値がそろった時点ですぐに停止しましょう。
よくある質問4
Top K Frequent Elements の時間計算量はどれくらいですか？
カウントには O(n) かかります。上位 k 個を選ぶコストは、異なる d 個の値をソートする場合は O(d log d)、サイズ k の最小ヒープを使う場合は O(d log k)、バケットソートを使う場合は O(n) に値域を1回走査するコストを加えたものになります。d は n に達することがあるため、最悪の場合、ソートは O(n log n) となり、バケットソートは線形時間です。
最頻出の上位K個の要素は、O(n)時間で解けますか？
はい、バケットソートを使えば可能です。カウントは1からnまでの整数なので、各値をそのカウントに対応するバケットに入れ、カウントの大きい順にバケットを読み取れば、比較ソートを使わずに頻度順に値を並べられます。カウントに対するクイックセレクトも平均ではO(n)ですが、最悪の場合は二次時間になります。
なぜ最大ヒープではなく最小ヒープを使うのでしょうか？
すべてのd個の値からなる最大ヒープを使う方法もあります。O(d)で構築し、k回ポップするため、合計でO(d + k log d)です。サイズkの最小ヒープにはk個のエントリだけが保持され、値が1つずつ到着する場合に適しています。なぜなら、ヒープの先頭にある値が取り除く候補だからです。その代わり、答えは逆順に取り出されるため、結果は後ろから埋めていきます。
Top K Frequent Elementsでは、同順位をどのように処理しますか？
規則を1つ選び、全体でそれを適用します。ここでは、カウントが同じ場合は小さい値を先にすることで、答えが一意になります。ソートでは、カウントを比較し、次に値を比較します。ヒープでは、カウントが同じ2つの値のうち、大きい値のほうが優先度が低くなります。バケットソートでは、値の昇順にバケットを埋めれば、各バケット内はすでに同順位の順序になっています。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def topKFrequent(nums, k):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
nums = [4, 1, 4, 2, 1, 4, 3, 1, 4] k = 2
期待値
[4, 1]