【Python】配列の中で欠けている最小の正整数を見つける方法

数値のリスト nums が与えられたとき、その中に存在しない「最初の正の整数」、すなわち欠けている最小の正整数を見つける問題を考えます。配列には重複した値や負の数が含まれる可能性がある点に注意が必要です。

例えば、入力が nums = [0, 3, 1] の場合、出力は 2 となります。0・1・3 は存在しますが、2 だけが欠けているためです。

解決のアプローチ

この問題は、集合（set）を使うことでシンプルかつ効率的に解くことができます。手順は以下の通りです。

• nums から正の数のみを取り出して集合を作成する（負の数と重複は自動的に除外される）
• 集合が空の場合は、正の数が一つも存在しないため 1 を返す
• 1 から「集合のサイズ + 2」まで順番に確認し、集合に存在しない最初の値を返す

実装例（Pythonコード）

class Solution:
    def solve(self, nums):
        nums = set(num for num in nums if num > 0)

        if not nums:
            return 1
        for i in range(1, len(nums) + 2):
            if i not in nums:
                return i

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

入力

[0, 3, 1]

出力

2

計算量について

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) です（n は配列の要素数）。集合を使用することで、各値の存在確認を平均 O(1) で実行できる点が大きなポイントです。また、探索範囲を「サイズ + 2」まで設定しているのは、配列が [1, 2, ..., n] のように完全に連続しているケースでも、次の欠落値 n+1 を確実に検出できるようにするためです。