Pythonで配列が「ソート済み＋回転」状態かどうかを判定するプログラム

問題の概要

nums という配列が与えられたとき、その配列が「もともと非減少順（昇順）にソートされていたものを、何度か（0回でも可）回転させた結果」になっているかどうかを判定します。配列には重複した要素が含まれている場合もあります。

たとえば、入力が nums = [12,15,2,5,6,9] の場合、出力は True になります。これは、ソート済みの配列 [2,5,6,9,12,15] を右に2回転させると [12,15,2,5,6,9] になるためです。

解決のアプローチ

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

1. 変数 j を 0 に初期化します。
2. j が「配列の長さ − 1」未満であり、かつ nums[j] ≤ nums[j+1] が成り立っている間、j を 1 ずつ増やします。これにより、昇順が崩れる位置（境界）を見つけます。
3. res を、「インデックス j+1 以降の部分配列」と「先頭からインデックス j までの部分配列」を連結したものとして作成します。これで回転前の状態に戻した配列が得られます。
4. i を 0 から res の長さ − 2 まで動かしながら確認し、res[i] > res[i+1] となる箇所があれば False を返します。
5. 最後まで昇順が崩れなければ、True を返します。

Pythonでの実装例

理解を深めるために、以下の実装例を見てみましょう。

def solve(nums):
    j = 0
    while (j < len(nums) - 1 and nums[j] <= nums[j + 1]):
        j += 1
    res = nums[j + 1 : len(nums)] + nums[0:j + 1]
    for i in range(len(res) - 1):
        if res[i] > res[i + 1]:
            return False
    return True

nums = [12,15,2,5,6,9]
print(solve(nums))

入力

[12,15,2,5,6,9]

出力

True

アルゴリズムのポイント

このアルゴリズムでは、まず昇順が崩れる最初の位置を特定し、そこで配列を分割して連結し直すことで「回転を解除」します。そのうえで全体が再び昇順になっていれば、元の配列は「ソート済み＋回転」だったことになります。

計算量は O(n)、追加で必要なメモリも O(n)（連結用の新しい配列 res を作成するため）です。重複要素があっても比較条件に「≤」を使っているため、正しく判定できる点も特徴です。