Peak Element ในอาร์เรย์ 2 มิติ

มีการกล่าวถึงรายการว่าเป็นองค์ประกอบสูงสุดเมื่อมีค่ามากกว่าหรือเท่ากับเพื่อนบ้านทั้งสี่ขององค์ประกอบนั้น องค์ประกอบข้างเคียงคือองค์ประกอบด้านบน ด้านล่าง ด้านซ้ายและด้านขวา สำหรับปัญหานี้เราจะพิจารณาถึงขอบเขตบางอย่าง องค์ประกอบในแนวทแยงจะไม่ถูกตรวจสอบเป็นองค์ประกอบข้างเคียง อาจมีองค์ประกอบพีคมากกว่าหนึ่งรายการในเมทริกซ์ และองค์ประกอบพีคไม่จำเป็นต้องเป็นองค์ประกอบที่ใหญ่ที่สุดในเมทริกซ์

อินพุตและเอาต์พุต

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