Un elemento es un elemento pico si es mayor o igual que sus cuatro vecinos, izquierdo, derecho, superior e inferior. Por ejemplo, los vecinos de A[i][j] son A[i-1][j], A[i+1][j], A[i][j-1] y A[i][j+1 ]. Para los elementos de esquina, los vecinos que faltan se consideran de valor infinito negativo.
Ejemplos:
Input : 10 20 15
21 30 14
7 16 32
Output : 30
30 is a peak element because all its
neighbors are smaller or equal to it.
32 can also be picked as a peak.
Input : 10 7
11 17
Output : 17
A continuación se presentan algunos datos sobre este problema:
- Una Diagonal adyacente no se considera como vecina.
- Un elemento pico no es necesariamente el elemento máximo.
- Puede existir más de uno de estos elementos.
- Siempre hay un elemento cumbre. Podemos ver esta propiedad creando algunas arrays con lápiz y papel.
Método 1: (Fuerza bruta) :
Iterar a través de todos los elementos de Matrix y verificar si es mayor/igual a todos sus vecinos. En caso afirmativo, devuelva el elemento.
Complejidad de tiempo: O(filas * columnas)
Espacio auxiliar: O(1)
Método 2: (Eficiente):
Este problema es principalmente una extensión de Find a peak element in 1D array . Aplicamos una solución similar basada en búsqueda binaria aquí.
- Considere la mitad de la columna y encuentre el elemento máximo en ella.
- Deje que el índice de la mitad de la columna sea ‘mid’, el valor del elemento máximo en la mitad de la columna sea ‘max’ y el elemento máximo esté en ‘mat[max_index][mid]’.
- Si max >= A[index][mid-1] & max >= A[index][pick+1], max es un pico, devuelve max.
- Si max < mat[max_index][mid-1], se repite para la mitad izquierda de la array.
- Si max < mat[max_index][mid+1], se repite para la mitad derecha de la array.
A continuación se muestra la implementación del algoritmo anterior:
C++
// Finding peak element in a 2D Array.
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
// Function to find the maximum in column 'mid'
// 'rows' is number of rows.
int findMax(int arr[][MAX], int rows, int mid, int& max)
{
int max_index = 0;
for (int i = 0; i < rows; i++) {
if (max < arr[i][mid]) {
// Saving global maximum and its index
// to check its neighbours
max = arr[i][mid];
max_index = i;
}
}
return max_index;
}
// Function to find a peak element
int findPeakRec(int arr[][MAX], int rows, int columns,
int mid)
{
// Evaluating maximum of mid column. Note max is
// passed by reference.
int max = 0;
int max_index = findMax(arr, rows, mid, max);
// If we are on the first or last column,
// max is a peak
if (mid == 0 || mid == columns - 1)
return max;
// If mid column maximum is also peak
if (max >= arr[max_index][mid - 1] && max >= arr[max_index][mid + 1])
return max;
// If max is less than its left
if (max < arr[max_index][mid - 1])
return findPeakRec(arr, rows, columns, mid - ceil((double)mid / 2));
// If max is less than its left
// if (max < arr[max_index][mid+1])
return findPeakRec(arr, rows, columns, mid + ceil((double)mid / 2));
}
// A wrapper over findPeakRec()
int findPeak(int arr[][MAX], int rows, int columns)
{
return findPeakRec(arr, rows, columns, columns / 2);
}
// Driver Code
int main()
{
int arr[][MAX] = { { 10, 8, 10, 10 },
{ 14, 13, 12, 11 },
{ 15, 9, 11, 21 },
{ 16, 17, 19, 20 } };
// Number of Columns
int rows = 4, columns = 4;
cout << findPeak(arr, rows, columns);
return 0;
}
Java
// Finding peak element in a 2D Array.
class GFG
{
static int MAX = 100;
// Function to find the maximum in column
// 'mid', 'rows' is number of rows.
static int findMax(int[][] arr, int rows,
int mid, int max)
{
int max_index = 0;
for (int i = 0; i < rows; i++)
{
if (max < arr[i][mid])
{
// Saving global maximum and its index
// to check its neighbours
max = arr[i][mid];
max_index = i;
}
}
return max_index;
}
// Function to change the value of [max]
static int Max(int[][] arr, int rows,
int mid, int max)
{
for (int i = 0; i < rows; i++)
{
if (max < arr[i][mid])
{
// Saving global maximum and its index
// to check its neighbours
max = arr[i][mid];
}
}
return max;
}
// Function to find a peak element
static int findPeakRec(int[][] arr, int rows,
int columns, int mid)
{
// Evaluating maximum of mid column.
// Note max is passed by reference.
int max = 0;
int max_index = findMax(arr, rows, mid, max);
max = Max(arr, rows, mid, max);
// If we are on the first or last column,
// max is a peak
if (mid == 0 || mid == columns - 1)
return max;
// If mid column maximum is also peak
if (max >= arr[max_index][mid - 1] &&
max >= arr[max_index][mid + 1])
return max;
// If max is less than its left
if (max < arr[max_index][mid - 1])
return findPeakRec(arr, rows, columns,
(int)(mid - Math.ceil((double) mid / 2)));
// If max is less than its left
// if (max < arr[max_index][mid+1])
return findPeakRec(arr, rows, columns,
(int)(mid + Math.ceil((double) mid / 2)));
}
// A wrapper over findPeakRec()
static int findPeak(int[][] arr, int rows, int columns)
{
return findPeakRec(arr, rows, columns, columns / 2);
}
// Driver Code
public static void main(String[] args)
{
int[][] arr = {{ 10, 8, 10, 10 },
{ 14, 13, 12, 11 },
{ 15, 9, 11, 21 },
{ 16, 17, 19, 20 }};
// Number of Columns
int rows = 4, columns = 4;
System.out.println(findPeak(arr, rows, columns));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Finding peak element in a 2D Array. MAX = 100 from math import ceil # Function to find the maximum in column 'mid' # 'rows' is number of rows. def findMax(arr, rows, mid,max): max_index = 0 for i in range(rows): if (max < arr[i][mid]): # Saving global maximum and its index # to check its neighbours max = arr[i][mid] max_index = i #print(max_index) return max,max_index # Function to find a peak element def findPeakRec(arr, rows, columns,mid): # Evaluating maximum of mid column. # Note max is passed by reference. max = 0 max, max_index = findMax(arr, rows, mid, max) # If we are on the first or last column, # max is a peak if (mid == 0 or mid == columns - 1): return max # If mid column maximum is also peak if (max >= arr[max_index][mid - 1] and max >= arr[max_index][mid + 1]): return max # If max is less than its left if (max < arr[max_index][mid - 1]): return findPeakRec(arr, rows, columns, mid - ceil(mid / 2.0)) # If max is less than its left # if (max < arr[max_index][mid+1]) return findPeakRec(arr, rows, columns, mid + ceil(mid / 2.0)) # A wrapper over findPeakRec() def findPeak(arr, rows, columns): return findPeakRec(arr, rows, columns, columns // 2) # Driver Code arr = [ [ 10, 8, 10, 10 ], [ 14, 13, 12, 11 ], [ 15, 9, 11, 21 ], [ 16, 17, 19, 20 ] ] # Number of Columns rows = 4 columns = 4 print(findPeak(arr, rows, columns)) # This code is contributed by Mohit Kumar
C#
// Finding peak element in a 2D Array.
using System;
class GFG
{
// Function to find the maximum in column
// 'mid', 'rows' is number of rows.
static int findMax(int[,] arr, int rows,
int mid, int max)
{
int max_index = 0;
for (int i = 0; i < rows; i++)
{
if (max < arr[i,mid])
{
// Saving global maximum and its
// index to check its neighbours
max = arr[i,mid];
max_index = i;
}
}
return max_index;
}
// Function to change the value of [max]
static int Max(int[,] arr, int rows,
int mid, int max)
{
for (int i = 0; i < rows; i++)
{
if (max < arr[i, mid])
{
// Saving global maximum and its
// index to check its neighbours
max = arr[i, mid];
}
}
return max;
}
// Function to find a peak element
static int findPeakRec(int[,] arr, int rows,
int columns, int mid)
{
// Evaluating maximum of mid column.
// Note max is passed by reference.
int max = 0;
int max_index = findMax(arr, rows, mid, max);
max = Max(arr, rows, mid, max);
// If we are on the first or last column,
// max is a peak
if (mid == 0 || mid == columns - 1)
return max;
// If mid column maximum is also peak
if (max >= arr[max_index, mid - 1] &&
max >= arr[max_index, mid + 1])
return max;
// If max is less than its left
if (max < arr[max_index,mid - 1])
return findPeakRec(arr, rows, columns,
(int)(mid - Math.Ceiling((double) mid / 2)));
// If max is less than its left
// if (max < arr[max_index][mid+1])
return findPeakRec(arr, rows, columns,
(int)(mid + Math.Ceiling((double) mid / 2)));
}
// A wrapper over findPeakRec()
static int findPeak(int[,] arr,
int rows, int columns)
{
return findPeakRec(arr, rows, columns,
columns / 2);
}
// Driver Code
static public void Main ()
{
int[,] arr = {{ 10, 8, 10, 10 },
{ 14, 13, 12, 11 },
{ 15, 9, 11, 21 },
{ 16, 17, 19, 20 }};
// Number of Columns
int rows = 4, columns = 4;
Console.Write(findPeak(arr, rows, columns));
}
}
// This code is contributed by ajit.
Javascript
<script>
// Finding peak element in a 2D Array.
let MAX = 100;
// Function to find the maximum in column
// 'mid', 'rows' is number of rows.
function findMax(arr, rows, mid, max)
{
let max_index = 0;
for (let i = 0; i < rows; i++)
{
if (max < arr[i][mid])
{
// Saving global maximum and its index
// to check its neighbours
max = arr[i][mid];
max_index = i;
}
}
return max_index;
}
// Function to change the value of [max]
function Max(arr, rows, mid, max)
{
for (let i = 0; i < rows; i++)
{
if (max < arr[i][mid])
{
// Saving global maximum and its index
// to check its neighbours
max = arr[i][mid];
}
}
return max;
}
// Function to find a peak element
function findPeakRec(arr, rows, columns, mid)
{
// Evaluating maximum of mid column.
// Note max is passed by reference.
let max = 0;
let max_index = findMax(arr, rows, mid, max);
max = Max(arr, rows, mid, max);
// If we are on the first or last column,
// max is a peak
if (mid == 0 || mid == columns - 1)
return max;
// If mid column maximum is also peak
if (max >= arr[max_index][mid - 1] &&
max >= arr[max_index][mid + 1])
return max;
// If max is less than its left
if (max < arr[max_index][mid - 1])
return findPeakRec(arr, rows, columns, (mid - Math.ceil(mid / 2)));
// If max is less than its left
// if (max < arr[max_index][mid+1])
return findPeakRec(arr, rows, columns, (mid + Math.ceil(mid / 2)));
}
// A wrapper over findPeakRec()
function findPeak(arr, rows, columns)
{
return findPeakRec(arr, rows, columns, parseInt(columns / 2, 10));
}
let arr = [[ 10, 8, 10, 10 ],
[ 14, 13, 12, 11 ],
[ 15, 9, 11, 21 ],
[ 16, 17, 19, 20 ]];
// Number of Columns
let rows = 4, columns = 4;
document.write(findPeak(arr, rows, columns));
</script>
Producción
21
Complejidad de tiempo: O(filas * registro(columnas)) . Recurrimos a la mitad del número de columnas. En cada llamada recursiva, buscamos linealmente el máximo en la columna central actual.
Espacio auxiliar: O (columnas/2) para pila de llamadas recursivas
Este artículo es una contribución de Rohit Thapliyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA