C++で2次元配列のピーク要素を検索する方法

はじめに

このチュートリアルでは、2次元配列からピーク要素を見つけ出すプログラムをC++で作成していきます。

「ピーク要素」とは、上下左右に隣接するすべての要素よりも大きい値を持つ要素のことです。配列内にはピーク要素が複数存在する場合がありますが、このプログラムでは見つかった最初のピーク要素を返します。

それでは、問題を解決するための手順を順番に見ていきましょう。

解決手順

• テスト用のダミーデータで2次元配列を初期化します。
• 2次元配列全体を走査します。
  • まず、配列の四隅（左上・右上・左下・右下）の要素をチェックします。四隅は隣接要素が2つしかないため、特別な処理が必要です。
• 次に、最初の行と最後の行に属する要素に対する条件を記述します。
• 続いて、最初の列と最後の列に属する要素に対する条件をチェックします。
• 最後に、それ以外の中間要素をチェックします。
• 各ケースにおいて、現在の要素を周囲の要素と比較します。比較対象は、上記の境界条件によって異なる点に注意してください。
• ピーク要素が見つかった時点で、その値を即座に返します。

サンプルコード

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

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

実行結果

上記のコードをコンパイルして実行すると、以下の出力が得られます。

7

コードの解説

このサンプルでは、4×4の2次元配列を走査し、各要素を隣接要素と比較しています。値「7」は3行目3列目に位置し、上下左右の隣接要素（4・3・5・5）すべてよりも大きいため、ピーク要素として判定されました。

なお、このアルゴリズムの計算量はO(rows × columns)となります。配列サイズが大きい場合は、二分探索を応用したO(rows × log(columns))の効率的な手法もありますので、興味のある方はぜひ調べてみてください。

まとめ

今回は、C++を使って2次元配列からピーク要素を検索する方法を学びました。境界部分と内部部分で比較条件が異なる点がポイントです。本チュートリアルについてご不明な点がある場合は、コメント欄でお気軽にお知らせください。