Pythonで連続する数値の区間を検出するプログラムの書き方

一意な（重複のない）数値のリスト nums が与えられたとします。このとき、nums 内で連続している数値をひとつの包括的な区間としてまとめ、ソート済みの2次元配列として出力することを目標とします。

たとえば、入力が nums = [10, 11, 12, 15, 16, 17, 28, 30] の場合、出力は [[10, 12], [15, 17], [28, 28], [30, 30]] となります。これは、10〜12 と 15〜17 がそれぞれ連続した数値のまとまりである一方、28 と 30 は前後の数値とつながっていないため、単独の区間 [28, 28]、[30, 30] として表現されるためです。

解決のための手順

この問題は、以下のステップで解くことができます。

• リスト nums を昇順にソートする
• nums の末尾に十分に大きな値（ここでは 1e9）を挿入し、「番兵」として機能させる
• 結果を格納する空のリスト ans を用意する
• 現在の区間の開始位置 l を nums[0] で初期化する
• i を 1 から nums のサイズまで繰り返す
  • nums[i] が nums[i-1] + 1 と等しくない場合（連続が途切れた場合）
    • 区間 [l, nums[i-1]] を ans の末尾に追加する
    • l を nums[i] に更新し、新しい区間の開始位置とする
• 最後に ans を返す

ポイントは、末尾に挿入した大きな値が「番兵」として働き、ループの最後で必ず区間を閉じる処理が実行される点です。これにより、最後の区間を別途処理する必要がなくなります。

それでは、実際の実装を見てみましょう。

実装例

class Solution:
   def solve(self, nums):
      nums.sort()
      nums.append(1e9)
      ans=[]
      l=nums[0]
      for i in range(1,len(nums)):
         if nums[i] != nums[i-1] + 1:
            ans.append([l, nums[i-1]])
            l=nums[i]
      return ans

ob = Solution()
nums = [10, 11, 12, 15, 16, 17, 28, 30]
print(ob.solve(nums))

入力

[10, 11, 12, 15, 16, 17, 28, 30]

出力

[[10, 12], [15, 17], [28, 28], [30, 30]]

計算量について

このアルゴリズムの時間計算量は O(n log n) です。全体の処理の中でソートが支配的なコストとなるためです。ソート済みのリストが与えられている場合は、線形時間 O(n) で処理できます。また、空間計算量は結果を格納するための O(n) となります。