0Pricing
Coding Interview Prep · レッスン

Map でグループ化とバケット分け

アナグラムや類似した項目をグループ化します

「Map でグループ化とバケット分け」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

グループ化というパターン

多くの問題では、共通点を持つ要素をグループ化する必要があります。キーからバケットへのマップを使えば、これを1回のすっきりした走査で処理できます。🗂️

グループ化のキーを選ぶ

重要なのは、同じグループの要素に対して同一になるキーを選ぶことです。ここを正しく選べば、残りの処理は簡単です。

defaultdict でバケット化する

defaultdict(list) を使うと、新しいキーごとに空のバケットが始まります。キーの存在を確認せずに要素を追加できます。

from collections import defaultdict
buckets = defaultdict(list)

基本のループ

各要素についてキーを計算し、そのキーのバケットに要素を追加します。要素ごとに1行の処理を行うだけで、すべてをグループ化できます。

for word in words:
    buckets[key_of(word)].append(word)

アナグラムをグループ化する

アナグラムは文字をソートした結果が同じなので、ソート後の文字列が最適なグループ化キーになります。1回ソートして、その結果でバケット化します。

k = ''.join(sorted(word))
buckets[k].append(word)

カウントにタプルキーを使う

ソートが遅い場合は、文字の出現回数をまとめた タプルもキーとして使えます。タプルはハッシュ可能なので、dict にそのまま格納できます。

k = tuple(Counter(word)[c] for c in 'abcdefghijklmnopqrstuvwxyz')

プロパティでバケット化する

キーを変えるだけで、数値を余り、偶奇、長さなどでグループ化できます。問題が変わっても、このパターンは同じです。

for n in nums:
    buckets[n % 3].append(n)

バケットソートの考え方

値が狭い範囲に収まる場合は、それぞれをインデックス付きのバケットに入れ、順番に読み取ります。これはほぼ線形時間で行えるソートです。

for x in nums:
    bucket[x].append(x)

結果を集める

バケット化した後、答えは通常、dict の値です。判定側がグループそのものを求めている場合は、リストに変換してください。

result = list(buckets.values())

グループごとに数える

グループのサイズだけが必要なら、Counter に入れるか、最後に長さを合計します。問題が実際に求めているものに合わせて選んでください。

sizes = {k: len(v) for k, v in buckets.items()}

マッピングが有利な理由

マップを使ったグループ化なら、すべてのペアを比較する代わりに O(n) で処理できます。ハッシュ化されたキーが照合を代わりに行ってくれます。

クイックチェック

アナグラムが同じバケットに入るように単語をグループ化したいとします。

まとめ

各要素のキーを defaultdict のバケットに対応付け、O(n) の1回の走査でグループ化します。キーをうまく選べば、グループ化の問題は簡単に解決できます。🚀

よくある質問

「Map でグループ化とバケット分け」レッスンは無料ですか？

はい。「Map でグループ化とバケット分け」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「Map でグループ化とバケット分け」で何を学びますか？

アナグラムや類似した項目をグループ化します ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。

「Map でグループ化とバケット分け」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 所属判定と重複排除のための集合
  2. ルックアップテーブルとしての辞書
  3. Counter と defaultdict の実践
  4. Map でグループ化とバケット分け
← Coding Interview Prepに戻る