Một mục được cho là phần tử đỉnh khi nó lớn hơn hoặc bằng với cả bốn lân cận của phần tử đó. Các phần tử lân cận là các phần tử trên cùng, dưới cùng, bên trái và bên phải. Đối với vấn đề này, chúng tôi sẽ xem xét một số giới hạn. Các phần tử đường chéo không được kiểm tra như các phần tử lân cận. Có thể có nhiều hơn một phần tử đỉnh trong ma trận và phần tử đỉnh không nhất thiết phải là phần tử lớn nhất trong ma trận.
Đầu vào và Đầu ra
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
Thuật toán
findMaxMid (hàng, giữa, tối đa)
Đầu vào: Số hàng của ma trận, hàng giữa, một phần tử tối đa làm đối số đầu ra.
Đầu ra: Cập nhật mục và chỉ mục tối đa của phần tử tối đa.
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 (hàng, cột, giữa)
Đầu vào - Hàng và cột của ma trận và vị trí hàng giữa.
Đầu ra - Phần tử đỉnh trong ma trận.
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
Ví dụ
#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);
} Đầu ra
The peak element is: 21