数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚
法律二维数组中的峰值元素
当一个元素大于或等于其四个相邻元素时，我们称之为峰值元素。其相邻元素包括上、下、左、右四个方向的元素。对于这个问题，我们将考虑一些边界情况。我们不会将对角线元素视为相邻元素。一个矩阵中可能存在多个峰值元素，而且峰值元素不一定就是矩阵中最大的元素。
输入和输出
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)
输入： 矩阵行数、中间行和一个输出参数的最大元素。
输出： 更新最大元素及其索引。
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
更新时间： 2020-06-16
962 次浏览
广告