Dada una array arr[] de tamaño n ≥ 3 , la tarea es encontrar la mínima diferencia posible entre el máximo y el mínimo elemento de la array después de eliminar un elemento.
Ejemplos:
Entrada: arr[] = {1, 2, 3}
Salida: 1
Eliminar 1 dará 3 – 2 = 1
Eliminar 2, 3 – 1 = 2
Y eliminar 3 dará como resultado 2 – 1 = 1
Entrada: arr[] = {1, 2, 4, 3, 4}
Salida: 2
Enfoque ingenuo: está claro que para tener un efecto en la diferencia solo se debe eliminar el elemento mínimo o máximo.
- Ordenar la array.
- Elimina el mínimo, almacena diff1 = arr[n – 1] – arr[1] .
- Elimina el máximo y diff2 = arr[n – 2] – arr[0] .
- Imprime min(diff1, diff2) al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum required difference
int findMinDifference(int arr[], int n)
{
// Sort the given array
sort(arr, arr + n);
// When minimum element is removed
int diff1 = arr[n - 1] - arr[1];
// When maximum element is removed
int diff2 = arr[n - 2] - arr[0];
// Return the minimum of diff1 and diff2
return min(diff1, diff2);
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 4, 3, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMinDifference(arr, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class solution
{
// Function to return the minimum required difference
static int findMinDifference(int arr[], int n)
{
// Sort the given array
Arrays.sort(arr);
// When minimum element is removed
int diff1 = arr[n - 1] - arr[1];
// When maximum element is removed
int diff2 = arr[n - 2] - arr[0];
// Return the minimum of diff1 and diff2
return Math.min(diff1, diff2);
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 1, 2, 4, 3, 4 };
int n = arr.length;
System.out.print(findMinDifference(arr, n));
}
}
// This code is contributed by
// Sanjit_Prasad
Python3
# Python3 implementation of the approach # Function to return the minimum # required difference def findMinDifference(arr, n) : # Sort the given array arr.sort() # When minimum element is removed diff1 = arr[n - 1] - arr[1] # When maximum element is removed diff2 = arr[n - 2] - arr[0] # Return the minimum of diff1 and diff2 return min(diff1, diff2) # Driver Code if __name__ == "__main__" : arr = [ 1, 2, 4, 3, 4 ] n = len(arr) print(findMinDifference(arr, n)) # This code is contributed by Ryuga
C#
// C# implementation of the approach
using System;
public class GFG{
// Function to return the minimum required difference
static int findMinDifference(int []arr, int n)
{
// Sort the given array
Array.Sort(arr);
// When minimum element is removed
int diff1 = arr[n - 1] - arr[1];
// When maximum element is removed
int diff2 = arr[n - 2] - arr[0];
// Return the minimum of diff1 and diff2
return Math.Min(diff1, diff2);
}
// Driver Code
static public void Main (){
int []arr = { 1, 2, 4, 3, 4 };
int n = arr.Length;
Console.Write(findMinDifference(arr, n));
}
}
// This code is contributed by Sachin..
PHP
<?php
// PHP implementation of the approach
// Function to return the minimum
// required difference
function findMinDifference($arr, $n)
{
// Sort the given array
sort($arr, 0);
// When minimum element is removed
$diff1 = $arr[$n - 1] - $arr[1];
// When maximum element is removed
$diff2 = $arr[$n - 2] - $arr[0];
// Return the minimum of diff1 and diff2
return min($diff1, $diff2);
}
// Driver Code
$arr = array(1, 2, 4, 3, 4);
$n = sizeof($arr);
echo findMinDifference($arr, $n);
// This code is contributed
// by Akanksha Rai
Javascript
<script>
// Javascript implementation of the approach
// Function to return the minimum required difference
function findMinDifference(arr, n)
{
// Sort the given array
arr.sort();
// When minimum element is removed
let diff1 = arr[n - 1] - arr[1];
// When maximum element is removed
let diff2 = arr[n - 2] - arr[0];
// Return the minimum of diff1 and diff2
return Math.min(diff1, diff2);
}
let arr = [ 1, 2, 4, 3, 4 ];
let n = arr.length;
document.write(findMinDifference(arr, n));
</script>
Producción:
2
Complejidad de tiempo: O (nlogn)
Espacio Auxiliar : O(1)
Enfoque eficiente: para encontrar los elementos min , secondMin , max y secondMax de la array. No necesitamos ordenar la array, se puede hacer en un solo recorrido de array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
// Function to return the minimum required difference
int findMinDifference(int arr[], int n)
{
int min__, secondMin, max__, secondMax;
min__ = secondMax = (arr[0] < arr[1]) ? arr[0] : arr[1];
max__ = secondMin = (arr[0] < arr[1]) ? arr[1] : arr[0];
for (int i = 2; i < n; i++)
{
// If current element is greater than max
if (arr[i] > max__)
{
// max will become secondMax
secondMax = max__;
// Update the max
max__ = arr[i];
}
// If current element is greater than secondMax
// but smaller than max
else if (arr[i] > secondMax)
{
// Update the secondMax
secondMax = arr[i];
}
// If current element is smaller than min
else if (arr[i] < min__)
{
// min will become secondMin
secondMin = min__;
// Update the min
min__ = arr[i];
}
// If current element is smaller than secondMin
// but greater than min
else if (arr[i] < secondMin) {
// Update the secondMin
secondMin = arr[i];
}
}
// Minimum of the two possible differences
int diff = min(max__ - secondMin, secondMax - min__);
return diff;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 4, 3, 4 };
int n = sizeof(arr)/sizeof(arr[0]);
cout << (findMinDifference(arr, n));
}
// This code is contributed by
// Shashank_Sharma
Java
// Java implementation of the approach
public class GFG {
// Function to return the minimum required difference
static int findMinDifference(int arr[], int n)
{
int min, secondMin, max, secondMax;
min = secondMax = (arr[0] < arr[1]) ? arr[0] : arr[1];
max = secondMin = (arr[0] < arr[1]) ? arr[1] : arr[0];
for (int i = 2; i < n; i++) {
// If current element is greater than max
if (arr[i] > max) {
// max will become secondMax
secondMax = max;
// Update the max
max = arr[i];
}
// If current element is greater than secondMax
// but smaller than max
else if (arr[i] > secondMax) {
// Update the secondMax
secondMax = arr[i];
}
// If current element is smaller than min
else if (arr[i] < min) {
// min will become secondMin
secondMin = min;
// Update the min
min = arr[i];
}
// If current element is smaller than secondMin
// but greater than min
else if (arr[i] < secondMin) {
// Update the secondMin
secondMin = arr[i];
}
}
// Minimum of the two possible differences
int diff = Math.min(max - secondMin, secondMax - min);
return diff;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 4, 3, 4 };
int n = arr.length;
System.out.println(findMinDifference(arr, n));
}
}
Python3
# Python 3 implementation of the approach # Function to return the minimum # required difference def findMinDifference(arr, n): if(arr[0] < arr[1]): min__ = secondMax = arr[0] else: min__ = secondMax = arr[1] if(arr[0] < arr[1]): max__ = secondMin = arr[1] else: max__ = secondMin = arr[0] for i in range(2, n): # If current element is greater # than max if (arr[i] > max__): # max will become secondMax secondMax = max__ # Update the max max__ = arr[i] # If current element is greater than # secondMax but smaller than max elif (arr[i] > secondMax): # Update the secondMax secondMax = arr[i] # If current element is smaller than min elif(arr[i] < min__): # min will become secondMin secondMin = min__ # Update the min min__ = arr[i] # If current element is smaller than # secondMin but greater than min elif(arr[i] < secondMin): # Update the secondMin secondMin = arr[i] # Minimum of the two possible # differences diff = min(max__ - secondMin, secondMax - min__) return diff # Driver code if __name__ == '__main__': arr = [1, 2, 4, 3, 4] n = len(arr) print(findMinDifference(arr, n)) # This code is contributed by # Surendra_Gangwar
C#
using System;
// C# implementation of the approach
public class GFG {
// Function to return the minimum required difference
static int findMinDifference(int []arr, int n)
{
int min, secondMin, max, secondMax;
min = secondMax = (arr[0] < arr[1]) ? arr[0] : arr[1];
max = secondMin = (arr[0] < arr[1]) ? arr[1] : arr[0];
for (int i = 2; i < n; i++) {
// If current element is greater than max
if (arr[i] > max) {
// max will become secondMax
secondMax = max;
// Update the max
max = arr[i];
}
// If current element is greater than secondMax
// but smaller than max
else if (arr[i] > secondMax) {
// Update the secondMax
secondMax = arr[i];
}
// If current element is smaller than min
else if (arr[i] < min) {
// min will become secondMin
secondMin = min;
// Update the min
min = arr[i];
}
// If current element is smaller than secondMin
// but greater than min
else if (arr[i] < secondMin) {
// Update the secondMin
secondMin = arr[i];
}
}
// Minimum of the two possible differences
int diff = Math.Min(max - secondMin, secondMax - min);
return diff;
}
// Driver code
public static void Main()
{
int []arr = { 1, 2, 4, 3, 4 };
int n = arr.Length;
Console.WriteLine(findMinDifference(arr, n));
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// PHP implementation of the approach
// Function to return the minimum
// required difference
function findMinDifference($arr, $n)
{
$min__ = $secondMax = ($arr[0] < $arr[1]) ?
$arr[0] : $arr[1];
$max__ = $secondMin = ($arr[0] < $arr[1]) ?
$arr[1] : $arr[0];
for ($i = 2; $i < $n; $i++)
{
// If current element is greater than max
if ($arr[$i] > $max__)
{
// max will become secondMax
$secondMax = $max__;
// Update the max
$max__ = $arr[$i];
}
// If current element is greater than secondMax
// but smaller than max
else if ($arr[$i] > $secondMax)
{
// Update the secondMax
$secondMax = $arr[$i];
}
// If current element is smaller than min
else if ($arr[$i] < $min__)
{
// min will become secondMin
$secondMin = $min__;
// Update the min
$min__ = $arr[$i];
}
// If current element is smaller than secondMin
// but greater than min
else if ($arr[$i] < $secondMin)
{
// Update the secondMin
$secondMin = $arr[$i];
}
}
// Minimum of the two possible differences
$diff = min($max__ - $secondMin,
$secondMax - $min__);
return $diff;
}
// Driver code
$arr = array( 1, 2, 4, 3, 4 );
$n = count($arr);
print(findMinDifference($arr, $n));
// This code is contributed by mits
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the minimum required difference
function findMinDifference(arr, n)
{
let min__, secondMin, max__, secondMax;
min__ = secondMax = (arr[0] < arr[1]) ? arr[0] : arr[1];
max__ = secondMin = (arr[0] < arr[1]) ? arr[1] : arr[0];
for (let i = 2; i < n; i++)
{
// If current element is greater than max
if (arr[i] > max__)
{
// max will become secondMax
secondMax = max__;
// Update the max
max__ = arr[i];
}
// If current element is greater than secondMax
// but smaller than max
else if (arr[i] > secondMax)
{
// Update the secondMax
secondMax = arr[i];
}
// If current element is smaller than min
else if (arr[i] < min__)
{
// min will become secondMin
secondMin = min__;
// Update the min
min__ = arr[i];
}
// If current element is smaller than secondMin
// but greater than min
else if (arr[i] < secondMin) {
// Update the secondMin
secondMin = arr[i];
}
}
// Minimum of the two possible differences
let diff = Math.min(max__ - secondMin, secondMax - min__);
return diff;
}
let arr = [ 1, 2, 4, 3, 4 ];
let n = arr.length;
document.write(findMinDifference(arr, n));
</script>
Complejidad de tiempo: O(n), para atravesar una array de tamaño n
Espacio auxiliar: O(1), ya que no se utiliza espacio adicional