set で重複を除去する｜コードで実践

set で重複を除去する

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

set は『中身が同じかどうか』だけを管理する箱

配列だけで重複を取り除こうとすると、典型的には次のような書き方になります

これは見た目はシンプルですが、v not in result が 配列の線形検索 なので O(n) です

set で重複を除去するとは

set を使って、整数配列から重複を取り除き、昇順ソート済みの配列を返す。本レッスンでは、set で重複を除去するの基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

ここまでで線形のデータ構造 (スタック / キュー) を見てきました。ここからは要素の集合を扱うデータ構造に入ります。最初に登場するのが set (集合) です。set は「同じ値を 2 度持たない」「順序を気にしない」のが特徴で、重複除去 や 存在判定 のために使われる、地味だけど超強力な道具です。

本レッスンでは整数配列 arr を受け取り、重複を取り除いた 配列を 昇順ソートして 返す関数 uniqueValues(arr) を実装します。実装の中で set を経由することで、重複除去 が O(n) で済む感覚を掴みましょう。

set は『中身が同じかどうか』だけを管理する箱。順序は気にせず、存在判定 と 重複除去 に圧倒的に強い。

なぜ set なのか

配列だけで重複を取り除こうとすると、典型的には次のような書き方になります。

Python

result = []
for v in arr:
    if v not in result:
        result.append(v)

これは見た目はシンプルですが、v not in result が 配列の線形検索 なので O(n) です。配列全体を回すので、合計で O(n^2) の計算量がかかります。要素数が 10000 なら、おおよそ 1 億回の比較が走り、現実的なアプリでは遅すぎます。

一方で set を使うと、存在チェック と 追加 がともに 平均 O(1) で済みます。これは内部的に ハッシュテーブル を持っているからで、要素数によらず一瞬で判定できます。set を一周通すだけで 重複除去 が O(n) で完了します。

配列だけで 重複除去 をすると O(n^2)、set を経由すれば O(n)。10000 要素なら 10000 倍違う。

アルゴリズム

diagram (will load when visible)

図のポイント (テキスト併記)

手順はとてもシンプルです

手順はとてもシンプルです。

set を 1 つ用意する
配列を 1 回走査し、各要素を set に追加する
set を配列に戻し、昇順にソートして返す

step 2 までで重複が除去され、step 3 で 戻り値の順序を確定 させます。set そのものは順序を持たないので、ソートしないとテストで期待値と一致しません。

Python での実装

Python

def uniqueValues(arr):
    return sorted(set(arr))

Python では set(arr) で一発で重複除去できます。sorted は新しいリストを返してくれるので 1 行で完結します。コードの短さは Python の データ構造リテラル の強みです。

JavaScript での実装

JavaScript

function uniqueValues(arr) {
  const set = new Set(arr);
  return [...set].sort((a, b) => a - b);
}

Set のコンストラクタに配列を渡すと、重複を除いた set が作れます。[...set] で配列に展開し、整数比較関数 (a, b) => a - b でソートします。比較関数を省略すると文字列比較 で並んでしまい、[1, 10, 2] のような変な順序になるので注意。

ハッシュテーブルが効くのは『中身を見るだけで、順序を気にしない』場面。逆に順序が大事なら配列やリンクリストに戻る。

Java / Go での実装

Java

import java.util.*;
public class Solution {
    public static int[] uniqueValues(int[] arr) {
        Set<Integer> set = new HashSet<>();
        for (int v : arr) set.add(v);
        List<Integer> list = new ArrayList<>(set);
        Collections.sort(list);
        int[] out = new int[list.size()];
        for (int i = 0; i < out.length; i++) out[i] = list.get(i);
        return out;
    }
}

Java は型が厳しいので、HashSet<Integer> → ArrayList<Integer> → Collections.sort → int[] という変換チェーンが必要です。それでも考え方は他言語と同じです。

よくある間違い

1 つ目は set の順序に期待してしまう こと。set はあくまで 集合 なので、要素の順序は保証されません (Python 3.7 以降の dict のように挿入順が保たれる実装もありますが、set は別)。必ず最後にソート して順序を確定します。

2 つ目は JS の sort の比較関数忘れ です。数値配列を arr.sort() だけで並べると文字列比較になり、[1, 10, 2] のように壊れます。整数比較は (a, b) => a - b を渡します。

3 つ目は 空配列のテスト を考えていないケース。uniqueValues([]) が空配列 [] を返すことを忘れずに。

やってみよう

[3, 1, 2, 1, 3] の結果が [1, 2, 3] になることを手で確認する。
文字列の配列 ['a', 'b', 'a'] でも同じロジックが動くか試す。Python の set はそのまま文字列を入れられる。
set を使わずに 配列だけ で同じ実装を書き、計算量が O(n^2) に劣化することを体感する。
set の intersection (積集合)、union (和集合)、difference (差集合) も Python で 1 行で書ける。試してみる。

よくある質問

Q. set とリストはどう違いますか？

A. set は重複を持たない集合で、要素の追加と存在確認が O(1) と高速です。リストは順序付きで重複を許し、要素の前後関係が意味を持つ場面で使います。重複除去や「含まれているか」判定の高速化が必要なら set が圧倒的に有利です。

Q. set の順序は保証されますか？

A. set は順序が保証されません。順序を保ったまま重複を除去したい場合は dict.fromkeys(items) を使う（Python）か、Set + 配列の組み合わせで管理してください。順序付きで集合演算したい場面は意外と多いので覚えておくと便利です。

Q. set 同士の積集合・和集合はどう書きますか？

A. a & b で積集合、a | b で和集合、a - b で差集合になります。リスト同士の共通要素を求めたいときは set(a) & set(b) で O(n) に高速化できます。文字列もイテラブルなので set('abc') & set('bcd') → {'b', 'c'} のように使えます。

次のレッスン

次は map で出現回数を数える に進みましょう。

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

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

理解度チェック (30 秒)

Q. 重複除去とは何か、1 文で説明してください。

この章のポイント

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

関連レッスン

set で重複を除去する