Pythonで、部分リストを並べ替えるだけでリスト全体が昇順にソートされる最短の範囲を見つける方法

数値のリスト nums が与えられたとき、その一部を並べ替えるだけでリスト全体が昇順にソートされるような、最短の部分リスト（サブリスト）の長さを求める問題について解説します。

問題の例

たとえば、入力が nums = [1, 2, 5, 4, 9, 10] の場合、出力は 2 になります。これは、部分リスト [5, 4] を並べ替えるだけで、リスト全体が [1, 2, 4, 5, 9, 10] という昇順の状態になるためです。

解き方のアルゴリズム

この問題は、次の手順で解くことができます。

• f := -1、l := -1 として初期化する
• lst := リスト nums をソートしたコピーを作成する
• i を 0 から nums のサイズまで繰り返す
  • nums[i] と lst[i] が異なる場合
    • f が -1 であれば、f := i を代入
    • それ以外の場合は、l := i を代入
• ループ終了後、l と f がどちらも -1 であれば 0 を返す（すでにソート済みであることを意味する）
• それ以外の場合は、l - f + 1 を返す

考え方のポイント

このアプローチの鍵となるのは、元のリストとソート済みリストを位置ごとに比較することです。最初に不一致が発生した位置が並べ替えが必要な範囲の始点となり、最後に不一致が発生した位置が終点となります。この2つの位置に挟まれた区間の長さが、求める答えになります。

実装例

以下の実装を見ると、理解がより深まるでしょう。

class Solution:
   def solve(self, nums):
      f = -1
      l = -1
      lst = sorted(nums)
      for i in range(len(nums)):
         if nums[i] != lst[i]:
            if f == -1:
               f = i
            else:
               l = i
      if l == -1 and f == -1:
         return 0
      return l - f + 1

ob = Solution()
print(ob.solve([1, 2, 5, 4, 9, 10]))

入力

[1, 2, 5, 4, 9, 10]

出力

2

計算量について

このアルゴリズムでは、リストのソートに O(n log n) の時間がかかるため、全体の時間計算量は O(n log n) となります。また、ソート済みのコピーを保持する必要があるため、空間計算量は O(n) です。