Dada una array, encuentre un elemento antes del cual todos los elementos sean más pequeños que él y después del cual todos sean más grandes que él. Devuelve el índice del elemento si existe tal elemento, de lo contrario, devuelve -1.
Ejemplos:
Entrada: arr[] = {5, 1, 4, 3, 6, 8, 10, 7, 9};
Salida: 4
Explicación: Todos los elementos a la izquierda de arr[4] son más pequeños que él
y todos los elementos a la derecha son mayores.Entrada: arr[] = {5, 1, 4, 4};
Salida: -1
Explicación: no existe tal índice.
Complejidad de tiempo esperada: O(n).
Una solución simple es considerar cada elemento uno por uno. Para cada elemento, compárelo con todos los elementos de la izquierda y todos los elementos de la derecha. La complejidad temporal de esta solución es O(n 2 ).
Una Solución Eficiente puede resolver este problema en O(n) tiempo usando O(n) espacio adicional. A continuación se muestra la solución detallada.
- Cree dos arrays leftMax[] y rightMin[].
- Atraviese la array de entrada de izquierda a derecha y complete leftMax[] de modo que leftMax[i] contenga un elemento máximo de 0 a i-1 en la array de entrada.
- Atraviese la array de entrada de derecha a izquierda y complete rightMin[] de modo que rightMin[i] contenga un elemento mínimo de n-1 a i+1 en la array de entrada.
- Array de entrada poligonal. Para cada elemento arr[i], compruebe si arr[i] es mayor que leftMax[i] y menor que rightMin[i]. En caso afirmativo, devuelva i.
La optimización adicional del enfoque anterior es usar solo una array adicional y atravesar la array de entrada solo dos veces. El primer recorrido es el mismo que el anterior y llena leftMax[]. El siguiente recorrido atraviesa desde la derecha y realiza un seguimiento del mínimo. El segundo recorrido también encuentra el elemento requerido.
La imagen de abajo es una ejecución en seco del enfoque anterior:
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find the element which is greater than
// all left elements and smaller than all right elements.
#include <bits/stdc++.h>
using namespace std;
// Function to return the index of the element which is greater than
// all left elements and smaller than all right elements.
int findElement(int arr[], int n)
{
// leftMax[i] stores maximum of arr[0..i-1]
int leftMax[n];
leftMax[0] = INT_MIN;
// Fill leftMax[1..n-1]
for (int i = 1; i < n; i++)
leftMax[i] = max(leftMax[i-1], arr[i-1]);
// Initialize minimum from right
int rightMin = INT_MAX;
// Traverse array from right
for (int i=n-1; i>=0; i--)
{
// Check if we found a required element
if (leftMax[i] < arr[i] && rightMin > arr[i])
return i;
// Update right minimum
rightMin = min(rightMin, arr[i]);
}
// If there was no element matching criteria
return -1;
}
// Driver program
int main()
{
int arr[] = {5, 1, 4, 3, 6, 8, 10, 7, 9};
int n = sizeof arr / sizeof arr[0];
cout << "Index of the element is " << findElement(arr, n);
return 0;
}
Java
// Java program to find the element which is greater than
// all left elements and smaller than all right elements.
import java.io.*;
import java.util.*;
public class GFG {
static int findElement(int[] arr, int n)
{
// leftMax[i] stores maximum of arr[0..i-1]
int[] leftMax = new int[n];
leftMax[0] = Integer.MIN_VALUE;
// Fill leftMax[1..n-1]
for (int i = 1; i < n; i++)
leftMax[i] = Math.max(leftMax[i - 1], arr[i - 1]);
// Initialize minimum from right
int rightMin = Integer.MAX_VALUE;
// Traverse array from right
for (int i = n - 1; i >= 0; i--)
{
// Check if we found a required element
if (leftMax[i] < arr[i] && rightMin > arr[i])
return i;
// Update right minimum
rightMin = Math.min(rightMin, arr[i]);
}
// If there was no element matching criteria
return -1;
}
// Driver code
public static void main(String args[])
{
int[] arr = {5, 1, 4, 3, 6, 8, 10, 7, 9};
int n = arr.length;
System.out.println("Index of the element is " +
findElement(arr, n));
}
// This code is contributed
// by rachana soma
}
Python3
# Python3 program to find the element which is greater than
# all left elements and smaller than all right elements.
def findElement(arr, n):
# leftMax[i] stores maximum of arr[0..i-1]
leftMax = [None] * n
leftMax[0] = arr[0]
# Fill leftMax[1..n-1]
for i in range(1, n):
leftMax[i] = max(leftMax[i-1], arr[i-1])
# Initialize minimum from right
rightMin = [None]*n
rightMin[n-1] = arr[n-1]
# Fill rightMin
for i in range(n-2, -1, -1):
rightMin[i] = min(rightMin[i+1], arr[i])
# Traverse array from right
for i in range(1, n-1):
# Check if we found a required element
# for ith element, it should be more than maximum of array
# elements [0....i-1] and should be less than the minimum of
# [i+1.....n-1] array elements
if leftMax[i-1] <= arr[i] and arr[i] <= rightMin[i+1]:
return i
# If there was no element matching criteria
return -1
# Driver program
if __name__ == "__main__":
arr = [5, 1, 4, 3, 6, 8, 10, 7, 9]
n = len(arr)
print("Index of the element is", findElement(arr, n))
# This code is contributed by Rituraj Jain
C#
// C# program to find the element which is greater than
// all left elements and smaller than all right elements.
using System;
class GFG
{
static int findElement(int[] arr, int n)
{
// leftMax[i] stores maximum of arr[0..i-1]
int[] leftMax = new int[n];
leftMax[0] = int.MinValue;
// Fill leftMax[1..n-1]
for (int i = 1; i < n; i++)
leftMax[i] = Math.Max(leftMax[i - 1], arr[i - 1]);
// Initialize minimum from right
int rightMin = int.MaxValue;
// Traverse array from right
for (int i=n-1; i>=0; i--)
{
// Check if we found a required element
if (leftMax[i] < arr[i] && rightMin > arr[i])
return i;
// Update right minimum
rightMin = Math.Min(rightMin, arr[i]);
}
// If there was no element matching criteria
return -1;
}
// Driver program
public static void Main()
{
int[] arr = {5, 1, 4, 3, 6, 8, 10, 7, 9};
int n = arr.Length;
Console.Write( "Index of the element is " + findElement(arr, n));
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
PHP
<?php
// PHP program to find the element
// which is greater than all left
// elements and smaller than all
// right elements.
function findElement($arr, $n)
{
// leftMax[i] stores maximum
// of arr[0..i-1]
$leftMax = array(0);
$leftMax[0] = PHP_INT_MIN;
// Fill leftMax[1..n-1]
for ($i = 1; $i < $n; $i++)
$leftMax[$i] = max($leftMax[$i - 1],
$arr[$i - 1]);
// Initialize minimum from right
$rightMin = PHP_INT_MAX;
// Traverse array from right
for ($i = $n - 1; $i >= 0; $i--)
{
// Check if we found a required
// element
if ($leftMax[$i] < $arr[$i] &&
$rightMin > $arr[$i])
return $i;
// Update right minimum
$rightMin = min($rightMin, $arr[$i]);
}
// If there was no element
// matching criteria
return -1;
}
// Driver Code
$arr = array(5, 1, 4, 3, 6, 8, 10, 7, 9);
$n = count($arr);
echo "Index of the element is " ,
findElement($arr, $n);
// This code is contributed
// by Sach_Code
?>
Javascript
<script>
// Javascript program to find the element
// which is greater than all left elements
// and smaller than all right elements.
// Function to return the index of the
// element which is greater than all
// left elements and smaller than all right elements.
function findElement(arr, n)
{
// leftMax[i] stores maximum of arr[0..i-1]
var leftMax = Array(n).fill(0);
leftMax[0] = Number.MIN_VALUE;
// Fill leftMax[1..n-1]
for(i = 1; i < n; i++)
leftMax[i] = Math.max(leftMax[i - 1],
arr[i - 1]);
// Initialize minimum from right
var rightMin = Number.MAX_VALUE;
// Traverse array from right
for(i = n - 1; i >= 0; i--)
{
// Check if we found a required element
if (leftMax[i] < arr[i] &&
rightMin > arr[i])
return i;
// Update right minimum
rightMin = Math.min(rightMin, arr[i]);
}
// If there was no element
// matching criteria
return -1;
}
// Driver code
var arr = [ 5, 1, 4, 3, 6, 8, 10, 7, 9 ];
var n = arr.length;
document.write("Index of the element is " +
findElement(arr, n));
// This code is contributed by aashish1995
</script>
Producción:
Index of the element is 4
Complejidad de tiempo: O(n)
Espacio auxiliar: O(n)
Gracias a Gaurav Ahirwar por sugerir la solución anterior.
Enfoque de espacio optimizado:
C++
// C++ program to find the element which is greater than
// all left elements and smaller than all right elements.
#include <bits/stdc++.h>
using namespace std;
int findElement(int a[], int n)
{
// Base case
if (n == 1 || n == 2) {
return -1;
}
// 1.element is the possible candidate for the solution
// of the problem.
// 2.idx is the index of the possible
// candidate.
// 3.maxx is the value which is maximum on the
// left side of the array.
// 4.bit tell whether the loop is
// terminated from the if condition or from the else
// condition when loop do not satisfied the condition.
// 5.check is the variable which tell whether the
// element is updated or not
int element = a[0], maxx = a[0], bit = -1, check = 0;
int idx = -1;
// The extreme two of the array can not be the solution
// Therefore iterate the loop from i = 1 to < n-1
for (int i = 1; i < (n - 1);) {
// here we find the possible candidate where Element
// with left side smaller and right side greater.
// when the if condition fail we check and update in
// else condition.
if (a[i] < maxx && i < (n - 1)) {
i++;
bit = 0;
}
// here we update the possible element if the
// element is greater than the maxx (maximum element
// so far). In while loop we sur-pass the value which
// is greater than the element
else {
if (a[i] >= maxx) {
element = a[i];
idx = i;
check = 1;
maxx = a[i];
}
if (check == 1) {
i++;
}
bit = 1;
while (a[i] >= element && i < (n - 1)) {
if (a[i] > maxx) {
maxx = a[i];
}
i++;
}
check = 0;
}
}
// checking for the last value and whether the loop is
// terminated from else or if block.
if (element <= a[n - 1] && bit == 1) {
return idx;
}
else {
return -1;
}
}
// Driver Code
int main()
{
int arr[] = { 5, 1, 4, 3, 6, 8, 10, 7, 9 };
int n = sizeof arr / sizeof arr[0];
// Function Call
cout << "Index of the element is "
<< findElement(arr, n);
return 0;
}
Java
// Java program to find the element
// which is greater than all left
// elements and smaller than all
// right elements.
class GFG{
static int findElement(int []a, int n)
{
// Base case
if (n == 1 || n == 2)
{
return -1;
}
// 1.element is the possible candidate for
// the solution of the problem.
// 2.idx is the index of the possible
// candidate.
// 3.maxx is the value which is maximum on the
// left side of the array.
// 4.bit tell whether the loop is
// terminated from the if condition or from
// the else condition when loop do not
// satisfied the condition.
// 5.check is the variable which tell whether the
// element is updated or not
int element = a[0], maxx = a[0],
bit = -1, check = 0;
int idx = -1;
// The extreme two of the array can
// not be the solution. Therefore
// iterate the loop from i = 1 to < n-1
for(int i = 1; i < (n - 1);)
{
// Here we find the possible candidate
// where Element with left side smaller
// and right side greater. When the if
// condition fail we check and update in
// else condition.
if (a[i] < maxx && i < (n - 1))
{
i++;
bit = 0;
}
// Here we update the possible element
// if the element is greater than the
// maxx (maximum element so far). In
// while loop we sur-pass the value which
// is greater than the element
else
{
if (a[i] >= maxx)
{
element = a[i];
idx = i;
check = 1;
maxx = a[i];
}
if (check == 1)
{
i++;
}
bit = 1;
while (a[i] >= element && i < (n - 1))
{
if (a[i] > maxx)
{
maxx = a[i];
}
i++;
}
check = 0;
}
}
// Checking for the last value and whether
// the loop is terminated from else or
// if block.
if (element <= a[n - 1] && bit == 1)
{
return idx;
}
else
{
return -1;
}
}
// Driver code
public static void main(String []args)
{
int []arr = { 5, 1, 4, 3, 6, 8, 10, 7, 9 };
int n = arr.length;
System.out.println("Index of the element is " +
findElement(arr, n));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 program to find the element which
# is greater than all left elements and
# smaller than all right elements.
def findElement (a, n):
# Base case
if (n == 1 or n == 2):
return -1
# 1. element is the possible candidate
# for the solution of the problem
# 2. idx is the index of the
# possible candidate
# 3. maxx is the value which is maximum
# on the left side of the array
# 4. bit tell whether the loop is
# terminated from the if condition or
# from the else condition when loop do
# not satisfied the condition.
# 5. check is the variable which tell
# whether the element is updated or not
element, maxx, bit = a[0], a[0], -1
check = 0
idx = -1
# The extreme of the array can't be
# the solution Therefore iterate
# the loop from i = 1 to < n-1
i = 1
while (i < (n - 1)):
# Here we find the possible candidate
# where element with left side smaller
# and right side greater. when the if
# condition fail we check and update
# in else condition
if (a[i] < maxx and i < (n - 1)):
i += 1
bit = 0
# Here we update the possible element
# if the element is greater than the
# maxx (maximum element so far). In
# while loop we sur-pass the value
# which is greater than the element
else:
if (a[i] >= maxx):
element = a[i]
idx = i
check = 1
maxx = a[i]
if (check == 1):
i += 1
bit = 1
while (a[i] >= element and i < (n - 1)):
if (a[i] > maxx):
maxx = a[i]
i += 1
check = 0
# Checking for the last value and whether
# the loop is terminated from else or
# if block
if (element <= a[n - 1] and bit == 1):
return idx
else:
return -1
# Driver Code
if __name__ == '__main__':
arr = [ 5, 1, 4, 3,
6, 8, 10, 7, 9 ]
n = len(arr)
# Function call
print("Index of the element is",
findElement(arr, n))
# This code is contributed by himanshu77
C#
// C# program to find the element
// which is greater than all left
// elements and smaller than all
// right elements.
using System;
class GFG{
static int findElement(int []a, int n)
{
// Base case
if (n == 1 || n == 2)
{
return -1;
}
// 1.element is the possible candidate for
// the solution of the problem.
// 2.idx is the index of the possible
// candidate.
// 3.maxx is the value which is maximum on the
// left side of the array.
// 4.bit tell whether the loop is
// terminated from the if condition or from
// the else condition when loop do not
// satisfied the condition.
// 5.check is the variable which tell whether the
// element is updated or not
int element = a[0], maxx = a[0],
bit = -1, check = 0;
int idx = -1;
// The extreme two of the array can
// not be the solution. Therefore
// iterate the loop from i = 1 to < n-1
for(int i = 1; i < (n - 1);)
{
// Here we find the possible candidate
// where Element with left side smaller
// and right side greater. When the if
// condition fail we check and update in
// else condition.
if (a[i] < maxx && i < (n - 1))
{
i++;
bit = 0;
}
// Here we update the possible element
// if the element is greater than the
// maxx (maximum element so far). In
// while loop we sur-pass the value which
// is greater than the element
else
{
if (a[i] >= maxx)
{
element = a[i];
idx = i;
check = 1;
maxx = a[i];
}
if (check == 1)
{
i++;
}
bit = 1;
while (a[i] >= element && i < (n - 1))
{
if (a[i] > maxx)
{
maxx = a[i];
}
i++;
}
check = 0;
}
}
// Checking for the last value and whether
// the loop is terminated from else or
// if block.
if (element <= a[n - 1] && bit == 1)
{
return idx;
}
else
{
return -1;
}
}
// Driver code
public static void Main(string[] args)
{
int []arr = { 5, 1, 4, 3, 6, 8, 10, 7, 9 };
int n = arr.Length;
// Function Call
Console.Write("Index of the element is " +
findElement(arr, n));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// javascript program to find the element
// which is greater than all left
// elements and smaller than all
// right elements.
function findElement(a , n)
{
// Base case
if (n == 1 || n == 2)
{
return -1;
}
// 1.element is the possible candidate for
// the solution of the problem.
// 2.idx is the index of the possible
// candidate.
// 3.maxx is the value which is maximum on the
// left side of the array.
// 4.bit tell whether the loop is
// terminated from the if condition or from
// the else condition when loop do not
// satisfied the condition.
// 5.check is the variable which tell whether the
// element is updated or not
var element = a[0], maxx = a[0], bit = -1, check = 0;
var idx = -1;
// The extreme two of the array can
// not be the solution. Therefore
// iterate the loop from i = 1 to < n-1
for (i = 1; i < (n - 1);) {
// Here we find the possible candidate
// where Element with left side smaller
// and right side greater. When the if
// condition fail we check and update in
// else condition.
if (a[i] < maxx && i < (n - 1)) {
i++;
bit = 0;
}
// Here we update the possible element
// if the element is greater than the
// maxx (maximum element so far). In
// while loop we sur-pass the value which
// is greater than the element
else {
if (a[i] >= maxx) {
element = a[i];
idx = i;
check = 1;
maxx = a[i];
}
if (check == 1) {
i++;
}
bit = 1;
while (a[i] >= element && i < (n - 1)) {
if (a[i] > maxx) {
maxx = a[i];
}
i++;
}
check = 0;
}
}
// Checking for the last value and whether
// the loop is terminated from else or
// if block.
if (element <= a[n - 1] && bit == 1)
{
return idx;
}
else
{
return -1;
}
}
// Driver code
var arr = [ 5, 1, 4, 3, 6, 8, 10, 7, 9 ];
var n = arr.length;
document.write("Index of the element is " + findElement(arr, n));
// This code is contributed by gauravrajput1
</script>
Producción
Index of the element is 4
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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