কম্পিউটার

2D অ্যারেতে পিক এলিমেন্ট


একটি আইটেমকে একটি শীর্ষ উপাদান বলা হয় যখন এটি সেই উপাদানটির চারটি প্রতিবেশীর চেয়ে বড় বা সমান হয়৷ প্রতিবেশী উপাদান হল উপরের, নীচে, বাম এবং ডান উপাদান। এই সমস্যার জন্য, আমরা কিছু সীমা বিবেচনা করব। তির্যক উপাদান প্রতিবেশী উপাদান হিসাবে চেক করা হয় না. একটি ম্যাট্রিক্সে একাধিক পিক এলিমেন্ট থাকতে পারে এবং পিক এলিমেন্টটি ম্যাট্রিক্সের সবচেয়ে বড় উপাদান নয়।

ইনপুট এবং আউটপুট

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

  1. জাভাতে সংখ্যাগরিষ্ঠ উপাদান

  2. পাইথনে সংখ্যাগরিষ্ঠ উপাদান

  3. পাইথনে একটি অ্যারের মধ্যে Kth বৃহত্তম উপাদান

  4. পাইথনে পিক এলিমেন্ট খুঁজুন