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(행, 중간, 최대)

입력: 행렬의 행 번호, 중간 행, 출력 인수로 최대 요소입니다.

출력: 최대 항목 및 최대 요소의 인덱스를 업데이트합니다.

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(행, 열, 중간)

입력 - 행렬의 행과 열, 중간 행 위치입니다.

출력 - 매트릭스의 피크 요소입니다.

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