C++で配列のピーク要素を見つける方法

このチュートリアルでは、与えられた配列の中からピーク要素を見つけるプログラムをC++で作成します。

ピーク要素とは、その両隣にある要素よりも大きい（または等しい）値を持つ要素のことです。それでは、問題を解くための手順を順番に見ていきましょう。

解決手順

• ダミーデータで配列を初期化します。

• 最初の要素と最後の要素がピーク要素の条件を満たしているかどうかをチェックします。配列の端は隣接要素が1つしかないため、特別な扱いが必要です。

• 2番目の要素から配列を走査します。

  • 現在の要素が、直前の要素と直後の要素の両方以上であるかを確認します。

  • 上記の条件を満たした場合、その要素をピーク要素として返します。

• 結果を出力します。

サンプルコード

実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int findPeakElement(int arr[], int n) {
    if (n == 1) {
        return arr[0];
    }
    if (arr[0] >= arr[1]) {
        return arr[0];
    }
    if (arr[n - 1] >= arr[n - 2]) {
        return arr[n - 1];
    }
    for (int i = 1; i < n - 1; i++) {
        if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1]) {
            return arr[i];
        }
    }
    return arr[0];
}
int main() {
    int arr[] = { 1, 2, 5, 4, 7 };
    cout << findPeakElement(arr, 5) << endl;
    return 0;
}

実行結果

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

7

補足：計算量について

このアルゴリズムは配列を線形に走査するため、時間計算量は O(n) となります。また、追加のメモリを使用しないため、空間計算量は O(1) です。なお、配列がソート済みである場合など特定の条件下では、二分探索を用いることで O(log n) まで計算量を削減できる点にも注目しておきましょう。

まとめ

今回はC++を使って、配列からピーク要素を見つける方法を解説しました。境界要素の扱い方や隣接要素との比較ロジックは、配列操作の基本的なパターンなので、ぜひマスターしておいてください。

このチュートリアルについてご不明な点がある場合は、コメント欄でお気軽にお知らせください。