2Dアレイのピーク要素

アイテムは、その要素の4つの隣接要素すべて以上である場合、ピーク要素であると言われます。隣接する要素は、上、下、左、右の要素です。この問題については、いくつかの限界を検討します。対角要素は隣接要素としてチェックされません。マトリックス内に複数のピーク要素が存在する場合があり、ピーク要素は必ずしもマトリックス内で最大の要素であるとは限りません。

入力と出力

Input:
A matrix of different numbers.
10  8  10  10
14 13  12  11
15  9  11  11
15  9  11  21
16 17  19  20

Output:
The peak element of the matrix.
Here the peak element is: 21

アルゴリズム

findMaxMid（rows、mid、max）

入力： 行列の行番号、中央の行、出力引数としての最大要素。

出力： max要素のmaxアイテムとインデックスを更新します。

Begin
   maxIndex := 0
   for all rows r in the matrix, do
      if max < matrix[i, mid], then
         max = matrix[i, mid],
         maxIndex := r
   done
   return maxIndex
End

findPeakElement（rows、columns、mid）

入力- マトリックスの行と列、および中央の行の場所。

出力- マトリックスのピーク要素。

Begin
   maxMid := 0
   maxMidIndex := findMaxMid(rows, mid, maxMid)

   if mid is first or last column, then
      return maxMid

   if maxMid>= item of previous and next row for mid column, then
      return maxMid

   if maxMid is less than its left element, then
      res := findPeakElement(rows, columns, mid – mid/2)
      return res

   if maxMid is less than its right element, then
      res := findPeakElement(rows, columns, mid + mid/2)
      return res
End

例

#include<iostream>
#define M 4
#define N 4
using namespace std;

intarr[M][N] = {
   {10, 8, 10, 10},
   {14, 13, 12, 11},
   {15, 9, 11, 21},
   {16, 17, 19, 20}
};

intfindMaxMid(int rows, int mid, int&max) {
   intmaxIndex = 0;

   for (int i = 0; i < rows; i++) {    //find max element in the mid column
      if (max <arr[i][mid]) {
         max = arr[i][mid];
         maxIndex = i;
      }
   }
   return maxIndex;
}

intfindPeakElement(int rows, int columns, int mid) {
   intmaxMid = 0;
   intmaxMidIndex = findMaxMid(rows, mid, maxMid);

   if (mid == 0 || mid == columns-1)    //for first and last column, the maxMid is maximum
      return maxMid;
   // If maxMid is also peak
   if (maxMid>= arr[maxMidIndex][mid-1] &&maxMid>= arr[maxMidIndex][mid+1])
      return maxMid;

   if (maxMid<arr[maxMidIndex][mid-1])     // If maxMid is less than its left element
      return findPeakElement(rows, columns, mid - mid/2);
   return findPeakElement(rows, columns, mid+mid/2);
}

int main() {
   int row = 4, col = 4;
   cout<< "The peak element is: "<<findPeakElement(row, col, col/2);
}

出力

The peak element is: 21