map で出現回数を数える
map で出現回数を数える
このレッスンで分かること
- 配列の各要素が何回現れたかを数えるという作業は、データ分析の現場でも実装の現場でも頻出します
- 素朴に二重ループで書くと
O(n^2)になりますが、mapを使えば 1 パスで完了します- 関数
frequency(arr)は整数配列を受け取り、出現する値の最大頻度 (= もっとも多く現れた値の出現回数) を整数で返します
map で出現回数を数える とは
ハッシュマップ (dict / Map) を使って、整数配列の各値の出現回数を 1 パスで集計する。本レッスンでは、map で出現回数を数える の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
配列の各要素が何回現れたかを数えるという作業は、データ分析の現場でも実装の現場でも頻出します。アンケート集計、ログのエラーコード分類、テキスト中の単語頻度、これらは全部「出現回数を数える」という同じ操作です。本レッスンでは map (ハッシュマップ) を使って、O(n) で頻度集計を行う基本パターンを身につけます。
素朴に二重ループで書くと O(n^2) になりますが、map を使えば 1 パスで完了します。これは第 4 章のうち、最もよく実戦で書くコード の 1 つです。
配列の頻度集計は
map (dict / HashMap)の代表例。O(n^2)からO(n)に落とすための基本パターン。
仕様
関数 frequency(arr) は整数配列を受け取り、出現する値の最大頻度 (= もっとも多く現れた値の出現回数) を整数で返します。空配列のときは 0 を返します。たとえば [1, 2, 2, 3, 3, 3] の最大頻度は 3 です。
戻り値を「値」ではなく「頻度 (回数)」にする理由は、戻り値の型が整数 1 つで済み、テストが言語依存しないからです。中で使う map のキーが整数でも文字列でもよく、純粋に「頻度を数える」操作だけに集中できます。
アルゴリズム
手順は次のとおりです。
- 空の
mapを 1 つ用意する (キーは値、バリューは出現回数) - 配列を 1 度走査し、各要素
vに対しmap[v] += 1を行う - ループ中 (または後で) 最大頻度を求めて返す
ループ中で max を更新すれば、2 周目を回す必要はなく O(n) で終わります。
Python での実装
Python
def frequency(arr):
if not arr:
return 0
counts = {}
best = 0
for v in arr:
counts[v] = counts.get(v, 0) + 1
if counts[v] > best:
best = counts[v]
return bestcounts.get(v, 0) は キーが無ければ 0 を返す安全なアクセスです。counts[v] += 1 だけ書くと、初回アクセス時に KeyError になります。get(v, 0) か defaultdict(int) を使う癖 をつけましょう。Python なら collections.Counter を使えば 1 行ですが、ここでは原理を学ぶために自力で書きます。
JavaScript での実装
JavaScript
function frequency(arr) {
if (arr.length === 0) return 0;
const counts = new Map();
let best = 0;
for (const v of arr) {
const c = (counts.get(v) || 0) + 1;
counts.set(v, c);
if (c > best) best = c;
}
return best;
}Map は Object と違ってキーの型を保ったまま保存できます。整数キーをそのまま使えるので、競技プログラミング系の問題と相性が良いです。(counts.get(v) || 0) + 1 という書き方で、未登録キーを 0 扱いにします。
1 パスで集計しながら最大値も同時に更新できる点が、map パターンの真価。2 周しなくて良いのが嬉しい。
Java / Go での実装
Java
import java.util.*;
public class Solution {
public static int frequency(int[] arr) {
if (arr.length == 0) return 0;
Map<Integer, Integer> counts = new HashMap<>();
int best = 0;
for (int v : arr) {
int c = counts.getOrDefault(v, 0) + 1;
counts.put(v, c);
if (c > best) best = c;
}
return best;
}
}Java の Map.getOrDefault(key, default) は Python の dict.get(key, default) と同じ感覚で使えます。getOrDefault がなかった時代は if (map.containsKey(k)) を毎回書いていましたが、今は楽になりました。
計算量
ハッシュマップへの get と set は平均 O(1)。配列の長さを n とすると、ループは n 回で、各イテレーションは O(1)。よって全体は O(n) です。これを二重ループの O(n^2) で書くと、要素数が 10000 のとき 1 億回 の比較が走り、現実的なアプリでは耐えられない速度になります。
ハッシュマップの操作は平均
O(1)。配列の頻度集計はO(n)で終わる、これが基本中の基本。
よくある間違い
1 つ目は 未登録キーへの加算 です。counts[v] += 1 を最初に書くと、未登録キーで KeyError や NaN が出ます。get(v, 0) で初期値を補う こと。
2 つ目は 空配列の戻り値 を考えていないケース。最大頻度を聞かれているのに、best = 0 のまま空配列で何も走らないと 0 を返せて結果的に OK ですが、best の初期値を Infinity 系にしてしまうと壊れます。最初に空チェックを入れるのが安全です。
3 つ目は 2 周走らせてしまう こと。1 周目で集計、2 周目で max を取る書き方でも正解は出ますが、ループ内で同時に best を更新すれば 1 周で済みます。O(n) 自体は変わりませんが、定数倍が半分になります。
やってみよう
[1, 1, 2, 3, 3, 3, 4]の最大頻度が3(値3が 3 回) になることを手で追う。- 同じ map を使って 最頻値そのもの (頻度ではなく値) を返すバージョンも書いてみる。
collections.Counter(Python) や_.countBy(lodash) のような既製ライブラリを使ったバージョンと比較する。- map のキーを「数値そのもの」ではなく「
v % 10のような派生キー」にすると、グルーピングと頻度集計が同時にできる。試してみる。
よくある質問
Q. dict と Counter どちらを使うべきですか？
A. 原理を学ぶ段階では dict + get(v, 0) で自力実装するのがおすすめです。実務コードでは collections.Counter が簡潔で可読性も高いため積極的に使って問題ありません。Counter は dict のサブクラスなので、習得後に切り替えてもロジックの変更はほぼ不要です。
Q. キーが文字列でも整数でも同じように動きますか？
A. はい、ハッシュマップのキーはハッシュ可能なオブジェクトであれば何でも使えます。整数でも文字列でもタプルでも同じ操作で集計できます。JavaScript の Map はキーの型を保ったまま保存できるため、文字列 "1" と整数 1 が別キーとして扱われる点に注意してください。
Q. defaultdict と get() の使い分けは？
A. get(v, 0) はその場で初期値を指定するスタイルで、特別なインポートが不要です。defaultdict(int) はキーが存在しない場合に自動で 0 を補填するため、counts[v] += 1 とシンプルに書けます。どちらも正解ですが、初学者は get(v, 0) の方が何が起きているかを意識しやすいです。
Q. 最大頻度ではなく最頻値そのものが欲しいときはどうしますか？
A. 集計後に max(counts, key=counts.get) (Python) や [...counts.entries()].reduce((a, b) => b[1] > a[1] ? b : a)[0] (JavaScript) のように、バリューで比較してキーを取り出す方法が一般的です。Python では Counter.most_common(1)[0][0] が最もシンプルです。
次のレッスン
次は 二数の和 (map で O(n)) に進みましょう。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 出現回数 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 出現回数 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 整数を返す。最大頻度 (もっとも多く出た値の回数)
- map / HashMap / dict を使い、1 パスの O(n) で集計する
- 空配列のときは 0 を返す
入出力例
test-cases.txt
frequency([1,2,2,3,3,3]) → 3
frequency([1,2,3,4]) → 1
frequency([5,5,5,5,5]) → 5
frequency([7]) → 1
frequency([1,1,2,2]) → 2
frequency([-1,-1,-1,0,1]) → 3