C++で配列が「ソート済みかつ回転」されているか判定する方法

整数の配列が与えられたとき、その配列が昇順にソートされた状態から、ある位置で回転（ローテーション）されているかどうかを判定するのが本記事のテーマです。

問題の例

入力1：

N = [7, 8, 9, 4, 5, 6]

出力：

True

解説： 配列は昇順に並んでおり、3番目の位置を境に要素が回転しているため、この場合は True を返します。

入力2：

N = [1, 5, 7, 6, 2, 3]

出力：

False

解説： 配列は昇順にも並んでおらず、特定の位置での回転も行われていないため、出力は False になります。

解き方のアプローチ

配列の要素は昇順に並んでいるか、あるいはバラバラの順序になっています。もし配列が「ソート済みかつ回転済み」であれば、N[i] > N[i+1] を満たす箇所は必ず1つだけ存在します。それは回転の境界となる部分です。

そこで、配列内のすべての隣接ペアについてこの条件をチェックし、条件を満たす箇所の数をカウントします。カウントが1以下であれば True、そうでなければ False を返せばよいのです。

アルゴリズムの手順

• 配列の要素を入力として受け取ります。
• ブール関数 checkSortedandRotated(int *arr, int n) は、配列とそのサイズを引数に取り、配列がソート済みかつ回転済みであれば true を、そうでなければ false を返します。
• 配列全体を走査し、arr[i] > arr[(i + 1) % n] を満たす要素の数をカウントします。剰余演算 % n を使うことで、末尾と先頭の比較（回転の境界）も正しく処理できます。
• カウントが「1」以下であれば true を返し、それ以外の場合は false を返します。
• 結果を出力します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
bool checkSortedandRotated(int * arr, int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > arr[(i + 1) % n])
            count++;
    }
    return (count <= 1);
}
int main() {
    int arr[] = {5,6,7,1,2,3,4};
    int n = sizeof(arr) / sizeof(int);
    if (checkSortedandRotated(arr, n)) {
        cout << "True" << endl;
    } else {
        cout << "False" << endl;
    }
    return 0;
}

上記のコードを実行すると、次の出力が得られます。

出力

True

与えられた配列 [5, 6, 7, 1, 2, 3, 4] は、3番目の位置から回転されたソート済み配列であるため、この場合の出力は「True」となります。

計算量

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n) です。また、追加のメモリを必要としないため、空間計算量は O(1) となり、非常に効率的な手法と言えます。