Pythonで範囲内の最初に欠けている正の整数を見つけるプログラム

サイズnの、重複のないソート済み整数リストが与えられたとします。このとき、範囲[1からn+1]の中で配列に存在しない最初の正の整数を見つける必要があります。

例えば、入力が nums = [0,5,1] の場合、出力は2になります。これは、1から5の範囲において2が最初に欠けている数だからです。

解決のアプローチ

この問題を解くには、以下の手順に従います。

• 変数 target を1で初期化する
• 配列 arr の各要素 i について以下を繰り返す
  • i が target と等しい場合、target を1増やす（target := target + 1）
• ループ終了後、target の値を返す

このアルゴリズムは、配列を一度だけ走査するため、時間計算量はO(n)と非常に効率的です。ソート済みのリストを前提としているため、先頭から順に期待される値と比較していくだけで、欠けている最小の正の整数を特定できます。

実装例

理解を深めるために、以下の実装を見てみましょう。

class Solution:
    def solve(self, arr):
        target = 1
        for i in arr:
            if i == target:
                target += 1
        return target

ob = Solution()
nums = [0,5,1]
print(ob.solve(nums))

入力

[0,5,1]

出力

2

コードの解説

このプログラムでは、まず target を1に設定し、配列の要素を先頭から順に確認していきます。現在の要素が target と一致すれば、次に探すべき値として target をインクリメントします。一致しない要素が出てきた時点で、その target が範囲内で最初に欠けている正の整数となります。最後に target を返すことで答えが得られます。