Pythonで配列が「ソート済みかつ回転」しているかを判定する方法

問題の概要

n個の一意な値で構成される配列があるとします。この配列が「昇順にソートされた状態から回転した配列」であるかどうかを判定してください。ただし、少なくとも1回の回転が必要なため、完全にソートされただけの配列は「ソートかつ回転」とはみなされません。

たとえば、入力が nums = [4,5,6,8,1,3] の場合、出力は True になります。この配列を2回回転すると [1, 3, 4, 5, 6, 8] という昇順の配列になるためです。

アルゴリズムの考え方

回転されたソート配列の最大の特徴は、最小値を境に配列が2つの昇順部分に分かれることです。この性質を利用して、以下の手順で判定を行います。

1. 配列内の最小値 min_element と、そのインデックス min_index を求めます。
2. フラグ before_sorted を True で初期化し、先頭から min_index の直前までの要素が昇順になっているかを確認します。降順の箇所が見つかれば False にしてループを抜けます。
3. 同様に、フラグ after_sorted を True で初期化し、min_index + 1 から末尾までの要素が昇順になっているかを確認します。
4. before_sorted と after_sorted がどちらも True であり、かつ配列の最後の要素が先頭の要素より小さい（nums[-1] < nums[0]）場合に True を返します。それ以外は False を返します。

最後の条件 nums[-1] < nums[0] が重要なポイントです。この条件により、単にソートされただけで回転が行われていない配列を正しく除外できます。

実装例（Python）

def solve(nums):
    min_element = min(nums)
    min_index = nums.index(min_element)

    # 最小値より前の部分が昇順かどうかを確認
    before_sorted = True
    for i in range(1, min_index):
        if nums[i] < nums[i - 1]:
            before_sorted = False
            break

    # 最小値より後の部分が昇順かどうかを確認
    after_sorted = True
    for i in range(min_index + 1, len(nums)):
        if nums[i] < nums[i - 1]:
            after_sorted = False
            break

    # 両方の条件と回転の条件を満たすか判定
    if before_sorted and after_sorted and nums[-1] < nums[0]:
        return True
    else:
        return False

nums = [4, 5, 6, 8, 1, 3]
print(solve(nums))

入力

[4, 5, 6, 8, 1, 3]

出力

True

計算量について

このアルゴリズムは配列を最大2回走査するため、時間計算量は O(n) です。また、追加のデータ構造を使用しないため、空間計算量は O(1) で抑えられます。

まとめ

配列が「ソート済みかつ回転」しているかの判定は、最小値の位置を基準に前後の部分配列がそれぞれ昇順になっているか、そして配列の端同士の大小関係を確認することで効率的に行えます。一意な値を持つ配列を前提とすれば、O(n) の線形時間で確実に判定できるシンプルで実用的な手法です。