Pythonでリスト内のすべての1が連続して出現するかどうかをチェックする方法

少なくとも1つの要素の値が 1 である数値リスト nums が与えられたとします。このとき、リスト内のすべての 1 が連続して並んでいるかどうかを判定する問題を考えてみましょう。

たとえば、入力が nums = [8, 2, 1, 1, 1, 3, 5] の場合、1 は途中で途切れることなく連続して出現しているため、出力は True になります。

一方、入力が [8, 2, 1, 3, 1, 5] のような場合は、1 が離れて出現しているため、出力は False となります。

アルゴリズムの考え方

この問題は、状態を表すフラグ変数を1つ用意することで効率的に解けます。手順は以下の通りです。

• visited := 0 — フラグ変数を初期化します(0:まだ1を見ていない、1:現在1の連続の中、2:1の連続が一度終了した)。
• nums の各要素 x について以下を繰り返します。
• x が 1 の場合:
  • visited が 2(すでに1のグループが終了済み)であれば、False を返します。
  • そうでなければ visited を 1 に設定します。
• x が 1 以外で、かつ visited が 0 以外の場合:
  • visited を 2 に設定し、「1の連続が終了した」ことを記録します。
• ループが最後まで完了したら True を返します。

この方法なら、リストを一度走査するだけで判定できるため、時間計算量は O(n)、空間計算量は O(1) という非常に効率的な実装になります。

実装例

それでは、実際のPythonコードを見てみましょう。

def solve(nums):
   visited = 0
   for x in nums:
      if x == 1:
         if visited == 2:
            return False
         visited = 1
      elif visited:
         visited = 2
   return True

nums = [8, 2, 1, 1, 1, 3, 5]
print(solve(nums))

入力

[8, 2, 1, 1, 1, 3, 5]

出力

True

コードの解説

このコードでは、変数 visited が3つの状態を管理しています。

• 0:まだ 1 を一度も見ていない状態
• 1:現在 1 の連続の中にいる状態
• 2:1 の連続がすでに終了した状態

要素を順番に確認していき、1 の連続が終わった後(visited == 2)に再び 1 が出現した時点で False を返すことで、「すべての1が連続しているか」を正確に判定できます。最後まで問題がなければ True を返します。