キーでグループ化

生田 陸人
監修
LuaGate エンジニア / 現役エンジニア
編集 LuaGate編集部

キーでグループ化

このレッスンで分かること

  • データベースの GROUP BY や、JavaScript の Lodash の groupBy、Python の itertools.groupby でおなじみの グループ化 は、データを「あるキー」でまとめて束…
  • 関数 groupByParity(arr) は、整数配列 arr を受け取り、[偶数だけのリスト, 奇数だけのリスト] を返します
  • 返り値の 順序 が問題になる典型ケースなので、ここでは「偶数 → 奇数」「各リスト内は昇順」と明示します

キーでグループ化 とは

整数配列を 2 で割った余りでグループ化し、[偶数のソート済みリスト, 奇数のソート済みリスト] の形で返す。

データベースの GROUP BY や、JavaScript の Lodash の groupBy、Python の itertools.groupby でおなじみの グループ化 は、データを「あるキー」でまとめて束ねる操作です。たとえば学生のリストを「学年」でまとめる、注文を「商品カテゴリ」でまとめる、整数の配列を「偶数 / 奇数」でまとめるなど、業務でも頻出します。本レッスンでは hashmap を使ってグループ化を O(n) で行う基本パターンを身につけます。

グループ化は key -> list of values の hashmap を作る操作。ソートで実装すると O(n log n) だが、ハッシュなら O(n) で十分。

仕様

関数 groupByParity(arr) は、整数配列 arr を受け取り、[偶数だけのリスト, 奇数だけのリスト] を返します。各リストは昇順にソート済み であること。空配列ならそれぞれ空配列を入れた [[], []] を返します。

返り値の 順序 が問題になる典型ケースなので、ここでは「偶数 → 奇数」「各リスト内は昇順」と明示します。

アルゴリズム

手順は次の通りです。

  1. evens と odds の 2 つの可変リストを用意する (これも hashmap の 1 種で、キーが 0 と 1 の小さなマップと考えてよい)
  2. 配列を 1 度走査し、v % 2 == 0 なら evens へ、そうでなければ odds へ追加する
  3. それぞれを昇順にソートして [evens, odds] の形で返す

ソートが入るので厳密には O(n log n) ですが、グルーピング自体は O(n) です。

Mermaid で流れを確認

diagram (will load when visible)

Python での実装

Python

def groupByParity(arr): evens = [] odds = [] for v in arr: if v % 2 == 0: evens.append(v) else: odds.append(v) evens.sort() odds.sort() return [evens, odds]

Python は list.sort() が破壊的、sorted(list) が新しい配列を返します。どちらでも構いません。

JavaScript での実装

JavaScript

function groupByParity(arr) { const evens = []; const odds = []; for (const v of arr) { if (v % 2 === 0) evens.push(v); else odds.push(v); } evens.sort((a, b) => a - b); odds.sort((a, b) => a - b); return [evens, odds]; }

JavaScript の Array.prototype.sort() は 文字列比較がデフォルト なので、整数を比較するときは必ず (a, b) => a - b のような比較関数を渡してください。これを忘れると [10, 2, 1] を昇順にしたつもりが [1, 10, 2] になります。

負の数の余りに注意

JavaScript と Python では負の数に対する % の挙動が異なります。

  • Python の -3 % 2 は 1
  • JavaScript の -3 % 2 は -1

判定が v % 2 == 0 であれば偶奇は同じになりますが、v % 2 == 1 で奇数判定をすると JS / Java / Go で負の数が漏れます。「偶数か否か」のように 1 つの値だけ比較する のが安全です。

数値計算系の問題では言語ごとの % の挙動を必ず確認する。とくに JS の -3 % 2 == -1 は要注意。

よくある間違い

1 つ目は ソート忘れ。配列を push した順番に返してしまうとテストが落ちます。
2 つ目は JS の sort 比較関数忘れ。evens.sort() だけ書くと文字列比較で並びます。
3 つ目は [odds, evens] の 順序逆転。仕様で「偶数が先」と決めているので逆にしないこと。

やってみよう

  • 同じ仕組みで「3 で割った余り」によるグループ化 (3 グループ) を書いてみる。
  • グループ化の結果をオブジェクト { even: [...], odd: [...] } に変えてみる。実務では配列より dict のほうが分かりやすい場面が多い。
  • データベースの GROUP BY parity, COUNT(*) を実装するイメージで、{ even: 3, odd: 2 } を返すバージョンも書いてみる。

集合系の問題は 戻り値の順序 が暗黙の落とし穴。必ずソートしてから返す癖をつけよう。

よくある質問

Q. この内容は面接でよく聞かれますか？

A. コーディング面接の頻出範囲です。データ構造（リンクリスト・ツリー・グラフ）とアルゴリズム（DP・BFS/DFS）は IT 系大手の選考でほぼ確実に問われます。LeetCode の Top 100 にも該当問題が多数含まれます。

Q. 計算量と空間計算量はどっちを優先しますか？

A. 通常は時間計算量を優先し、空間が制約条件として明示されたら空間も考慮します。例えば「O(1) 空間で」と書かれていれば in-place アルゴリズム必須です。実務では時間 vs メモリのトレードオフを意識しつつ、ボトルネックを実測してから判断します。

Q. 問題が解けないときどう取り組めば良いですか？

A. まず小さな入力（n=3 程度）で手計算し、規則性を見つけます。次にナイーブ解（O(n²) でも可）を書き、最後に最適化します。いきなり最適解を狙うと手が止まりやすいので、段階的に進めるのが定石です。

次のレッスン

次は two sum (hash で O(n)) で、2 つの要素の和が目標値になるインデックスペアを hash を使って O(n) で探す方法を学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

  1. グループ化 の要点を自分の言葉で説明できる
  2. このレッスンの最小コード (または操作手順) を見ずに書ける
  3. 練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. グループ化 とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

要件

  1. 戻り値は [偶数の昇順リスト, 奇数の昇順リスト] の 2 要素配列
  2. 1 パスでグループに振り分けてから昇順ソートする (O(n log n))
  3. 空配列は [[], []] を返す

入出力例

test-cases.txt

groupByParity([3,1,2,4]) → [[2,4],[1,3]] groupByParity([1,2,3,4,5]) → [[2,4],[1,3,5]] groupByParity([2,4,6]) → [[2,4,6],[]] groupByParity([1,3,5]) → [[],[1,3,5]] groupByParity([10,7,8,3,1]) → [[8,10],[1,3,7]]

ヒント

main.py
main.py
学習モード

メモ

キーでグループ化

⌘S で保存