Pythonで最短の「ソートされていない連続部分配列」を見つける方法

整数配列が与えられたとき、「その部分配列だけを昇順にソートすれば、配列全体がソート済みの状態になる」という条件を満たす連続する部分配列の中で、最も短いものを求めてその長さを出力することを考えます。

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

解法のアプローチ

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

1. 元の配列 nums を昇順にソートしたコピー res を作成します。
2. 各インデックス i について nums[i] と res[i] を比較し、値が異なる場合はそのインデックスをリスト r に記録していきます。
3. r が空の場合、配列はすでにソート済みなので 0 を返します。
4. それ以外の場合、記録されたインデックスの範囲、すなわち r[-1] - r[0] + 1(最後の要素 − 最初の要素 + 1)が求める最短部分配列の長さとなります。

Pythonでの実装例

以下のコードで実際の動作を確認できます。

class Solution:
    def findUnsortedSubarray(self, nums):
        res = sorted(nums)
        r = []
        for i in range(len(res)):
            if nums[i] != res[i]:
                r.append(i)
        if len(r) == 0:
            return 0
        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

計算量の考察

この解法では、ソートに O(n log n)、全要素の比較に O(n) の時間が必要なため、全体の時間計算量は O(n log n) となります。また、ソート済みのコピーを保持するため、空間計算量は O(n) です。

なお、より効率化したい場合は、配列を左端と右端から一度ずつ走査し、順序が崩れている境界を直接特定する方法を使えば、O(n) 時間・O(1) 空間で解くことも可能です。