Pythonで整数配列の最長連続シーケンスの長さを求める方法

整数の配列が与えられたとき、その中に含まれる最も長い連続した数値のシーケンスの長さを求める問題を考えてみましょう。たとえば、入力が [100, 4, 250, 1, 3, 2] の場合、最長の連続シーケンスは [1, 2, 3, 4] となるため、答えは 4 になります。

解法のアプローチ

この問題を線形時間 O(n) で解くために、以下の手順に従います。

• まず配列をセット（集合）に変換し、変数 longest を 0 で初期化します。
• セット内の各要素 i について、「i - 1 がセットに存在しない場合」のみ処理を開始します。これは i が連続シーケンスの始点であることを意味します。
• 始点が見つかったら、current := i、streak := 0 として初期化し、i がセットに存在する間、i を 1 ずつ増やしながら streak をカウントアップしていきます。
• 各シーケンスの探索が終わるごとに、longest を longest と streak のうち大きい方の値で更新します。
• すべての要素を処理し終えたら、longest を結果として返します。

「i - 1 が存在しない場合のみ走査を開始する」という工夫がポイントです。これにより各要素は高々2回しか参照されないため、全体の計算量は O(n) に抑えられます。単純にソートしてから連続性を確認する方法では O(n log n) かかるため、この手法の方が効率的です。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

class Solution(object):
    def longestConsecutive(self, a):
        a = set(a)
        longest = 0
        for i in a:
            if i-1 not in a:
                current = i
                streak = 0
                while i in a:
                    i += 1
                    streak += 1
                    longest = max(longest, streak)
        return longest

ob = Solution()
print(ob.longestConsecutive([100,4,250,1,3,2]))

入力

[100,4,250,1,3,2]

出力

4

まとめ

このアルゴリズムでは、配列をセットに変換することで要素の存在確認を O(1) で行えるようにし、さらに各連続シーケンスの始点からのみ走査を開始することで無駄な計算を排除しています。その結果、時間計算量は O(n)、空間計算量は O(n) となり、大規模なデータに対しても効率的に動作します。重複する要素がある場合も、セット化の時点で自動的に除外されるため、正しく動作するのも利点です。