Se le proporciona una array de n elementos con la condición básica de que la ocurrencia del elemento más grande sea más de una vez. Tienes que encontrar la distancia mínima entre los máximos. (n>=2).
Ejemplos:
Input : arr[] = {3, 5, 2, 3, 5, 3, 5}
Output : Minimum Distance = 2
Explanation : Greatest element is 5 and its index
are 1, 4 and 6. Resulting minimum distance of 2
from position 4 to 6.
Input : arr[] = {1, 1, 1, 1, 1, 1}
Output : Minimum Distance = 1
Explanation : Greatest element is 1 and its index
are 0, 1, 2, 3, 4 and 5. Resulting minimum distance
of 1.
Un enfoque básico se ejecuta en O(n 2 ). Primero encontramos el elemento máximo. Luego, para cada elemento igual al elemento máximo, encontramos el elemento máximo más cercano.
Una solución eficiente termina nuestro trabajo en un solo recorrido de array. Inicializamos maximum_element = arr[0], min_distance = n e index = 0. Después de eso, para cada elemento, debemos verificar si el elemento es igual, mayor o menor que el elemento máximo. Dependiendo de tres casos, tenemos la siguiente opción:
- caso a: si el elemento es igual al elemento_máximo, actualice min_dis = min( min_dis , (i-index)) y actualice index = i;
- caso b: si el elemento es mayor que el elemento_máximo, actualice el elemento_máximo = arr[i], índice = i y min_dis = n.
- caso c: si el elemento es menor que el elemento_máximo, iterar al siguiente elemento.
C++
// C++ program to find Min distance
// of maximum element
#include<bits/stdc++.h>
using namespace std;
//function to return min distance
int minDistance (int arr[], int n)
{
int maximum_element = arr[0];
int min_dis = n;
int index = 0;
for (int i=1; i<n; i++)
{
// case a
if (maximum_element == arr[i])
{
min_dis = min(min_dis, (i-index));
index = i;
}
// case b
else if (maximum_element < arr[i])
{
maximum_element = arr[i];
min_dis = n;
index = i;
}
// case c
else
continue;
}
return min_dis;
}
// driver program
int main()
{
int arr[] = {6, 3, 1, 3, 6, 4, 6};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Minimum distance = "
<< minDistance(arr, n);
return 0;
}
Java
// Java program to find Min distance
// of maximum element
class GFG
{
// function to return min distance
static int minDistance (int arr[], int n)
{
int maximum_element = arr[0];
int min_dis = n;
int index = 0;
for (int i=1; i<n; i++)
{
// case a
if (maximum_element == arr[i])
{
min_dis = Math.min(min_dis, (i-index));
index = i;
}
// case b
else if (maximum_element < arr[i])
{
maximum_element = arr[i];
min_dis = n;
index = i;
}
// case c
else
continue;
}
return min_dis;
}
// Driver code
public static void main (String[] args)
{
int arr[] = {6, 3, 1, 3, 6, 4, 6};
int n = arr.length;
System.out.print("Minimum distance = "+minDistance(arr, n));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find Min
# distance of maximum element
# Function to return min distance
def minDistance (arr, n):
maximum_element = arr[0]
min_dis = n
index = 0
for i in range(1, n):
# case a
if (maximum_element == arr[i]):
min_dis = min(min_dis, (i - index))
index = i
# case b
elif (maximum_element < arr[i]):
maximum_element = arr[i]
min_dis = n
index = i
# case c
else:
continue
return min_dis
# driver program
arr = [6, 3, 1, 3, 6, 4, 6]
n = len(arr)
print("Minimum distance =", minDistance(arr, n))
# This code is contributed by Smitha Dinesh Semwal
C#
// C# program to find Min distance
// of maximum element
using System;
class GFG {
// function to return min distance
static int minDistance (int []arr, int n)
{
int maximum_element = arr[0];
int min_dis = n;
int index = 0;
for (int i = 1; i < n; i++)
{
// case a
if (maximum_element == arr[i])
{
min_dis = Math.Min(min_dis,
(i - index));
index = i;
}
// case b
else if (maximum_element < arr[i])
{
maximum_element = arr[i];
min_dis = n;
index = i;
}
// case c
else
continue;
}
return min_dis;
}
// Driver code
public static void Main ()
{
int []arr = {6, 3, 1, 3, 6, 4, 6};
int n = arr.Length;
Console.WriteLine("Minimum distance = "
+ minDistance(arr, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find Min distance
// of maximum element
//function to return min distance
function minDistance($arr, $n)
{
$maximum_element = $arr[0];
$min_dis = $n;
$index = 0;
for ($i = 1; $i < $n; $i++)
{
// case a
if ($maximum_element == $arr[$i])
{
$min_dis = min($min_dis, ($i - $index));
$index = $i;
}
// case b
else if ($maximum_element < $arr[$i])
{
$maximum_element = $arr[$i];
$min_dis = $n;
$index = $i;
}
// case c
else
continue;
}
return $min_dis;
}
// Driver Code
$arr = array(6, 3, 1, 3, 6, 4, 6);
$n = count($arr);
echo "Minimum distance = "
.minDistance($arr,$n);
// This code is contributed by Sam007
?>
Javascript
<script>
// JavaScript program to find Min distance
// of maximum element
// function to return min distance
function minDistance (arr, n)
{
let maximum_element = arr[0];
let min_dis = n;
let index = 0;
for (let i=1; i<n; i++)
{
// case a
if (maximum_element == arr[i])
{
min_dis = Math.min(min_dis, (i-index));
index = i;
}
// case b
else if (maximum_element < arr[i])
{
maximum_element = arr[i];
min_dis = n;
index = i;
}
// case c
else
continue;
}
return min_dis;
}
// Driver code
let arr = [6, 3, 1, 3, 6, 4, 6];
let n = arr.length;
document.write("Minimum distance = "+minDistance(arr, n));
</script>
Producción :
Minimum distance = 2
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA