【Python】配列全体をソートするために必要な最小長の未ソート部分配列を見つける方法

問題の概要

サイズ n のソートされていない配列 A[0..n-1] が与えられたとします。このとき、その部分配列だけをソートすれば配列全体が整った状態になるような、最小の長さを持つ部分配列 A[s..e] を見つける必要があります。

例えば、配列が [2,6,4,8,10,9,15] の場合、答えは 5 となり、該当する部分配列は [6,4,8,10,9] です。この部分配列を昇順に並び替えると、配列全体が完全にソートされます。

解決のアプローチ

この問題は、元の配列と「ソート済みの配列」を比較することで解けます。具体的には、以下の手順に従います。

• 元の配列 nums をソートした結果を res とします。
• インデックスを記録するための空リスト r を用意します。
• i を 0 から res の長さまでループさせます。
  • nums[i] と res[i] が一致しない場合、そのインデックス i を r に追加します。
• r の長さが 0 なら 0 を返します（配列は既にソート済み）。長さが 1 の場合も 1 を返します。
• それ以外の場合は、「r の最後の要素 − r の最初の要素 ＋ 1」を返します。これが求める最小の部分配列の長さです。

アルゴリズムのポイント

この手法の核心は、元の配列とソート後の配列を同じ位置同士で比較すると、順序が崩れている要素の位置が分かるという点です。一致しなかったインデックスのうち、最も左側のものから最も右側のものまでの範囲こそが、ソートによって全体が整う最小の区間になります。

計算量は、ソートに伴い時間 O(n log n)、比較用の配列確保により空間 O(n) となります。

実装例

以下の Python コードで実際の動作を確認してみましょう。

class Solution(object):
   def findUnsortedSubarray(self, nums):
      res = sorted(nums)
      ans = 0
      r = []
      for i in range(len(res)):
         if nums[i] != res[i]:
            r.append(i)
      if not len(r):
         return 0
      if len(r) == 1:
         return 1
      return r[-1]-r[0]+1
ob1 = Solution()
print(ob1.findUnsortedSubarray([2,6,4,8,10,9,15]))

入力

[2,6,4,8,10,9,15]

出力

5

まとめ

ソート済みのコピーとの比較によって、順序が崩れた区間の両端を特定するだけで、この問題はシンプルに解決できます。追加の複雑なロジックを必要としないため、理解しやすく実装もしやすいアプローチです。