Pythonでソート済みリストの範囲内から欠落している数値を検出する方法

ソート済みの数値リストが与えられたとき、その範囲の中でどの数値が欠落しているのかを調べたいケースはよくあります。本記事では、Pythonを使って欠落している数値を効率的に検出する2つの方法を紹介します。

方法1: range関数を活用する

1つ目の方法は、range関数を使ってリストの最初の要素から最後の要素までの連続した数値を生成し、リスト内包表記とnot in演算子を組み合わせて、元のリストに存在しない数値だけを抽出するアプローチです。

サンプルコード

listA = [1,5,6, 7,11,14]

# 元のリストを表示
print("Given list : ",listA)

# rangeを使って欠落要素を検出
res = [x for x in range(listA[0], listA[-1]+1)
                    if x not in listA]
# 結果を表示
print("Missing elements from the list : \n" ,res)

実行結果

上記のコードを実行すると、以下の出力が得られます。

Given list : [1, 5, 6, 7, 11, 14]
Missing elements from the list :
[2, 3, 4, 8, 9, 10, 12, 13]

処理のポイント

• listA[0]でリストの先頭の値、listA[-1]で末尾の値を取得します。
• range(listA[0], listA[-1]+1)により、先頭から末尾まで（末尾を含む）の全数値を走査します。
• if x not in listAの条件により、リストに含まれていない数値のみが結果に残ります。

この方法はコードが簡潔で読みやすいのが特徴ですが、リストが長くなるとnot inによる線形探索のコストが増えるため、大規模なデータには注意が必要です。

方法2: zip関数を活用する

2つ目の方法は、zip関数を使って隣接する要素同士をペア化し、その差分を確認するアプローチです。隣接する2つの要素の差が1より大きい場合、その間に欠落した数値が存在することになります。

サンプルコード

listA = [1,5,6, 7,11,14]

# 元のリストを表示
print("Given list : ",listA)

# zipを使って欠落要素を検出
res = []
for m,n in zip(listA,listA[1:]):
    if n - m > 1:
        for i in range(m+1,n):
            res.append(i)

# 結果を表示
print("Missing elements from the list : \n" ,res)

実行結果

上記のコードを実行すると、以下の出力が得られます。

Given list : [1, 5, 6, 7, 11, 14]
Missing elements from the list :
[2, 3, 4, 8, 9, 10, 12, 13]

処理のポイント

• zip(listA, listA[1:])により、リスト全体と1つずらしたリストをペアリングし、隣接要素の組み合わせ（例： (1,5), (5,6), (6,7)...）を作成します。
• n - m > 1という条件で、隣接要素の間隔が1より大きい箇所、つまり欠落がある箇所を特定します。
• range(m+1, n)で、その間に存在する欠落数値をすべて取り出して結果リストに追加します。

この方法はソート済みリストの性質を直接利用するため、リストが長い場合でも比較的効率的に動作します。また、欠落が発生している「区間」を明示的に判定できるため、ロジックの意図も把握しやすくなっています。

まとめ

どちらの方法も同じ結果 [2, 3, 4, 8, 9, 10, 12, 13] を返します。小規模なデータなら可読性の高いrange方式、パフォーマンスやロジックの明快さを重視するならzip方式を選ぶとよいでしょう。