Minimice las eliminaciones de cualquier extremo para eliminar el Mínimo y el Máximo de la array

Dada la array de enteros arr[] de tamaño N, la tarea es encontrar el recuento del número mínimo de operaciones de eliminación para eliminar el elemento mínimo y máximo de la array. Los elementos solo se pueden eliminar desde cualquier extremo de la array.

Ejemplos:

Entrada: arr = [2, 10, 7, 5, 4, 1, 8, 6]
Salida: 5
Explicación: El elemento mínimo es 1 y el elemento máximo es 10. Podemos visualizar las operaciones de eliminación de la siguiente manera:
[2, 10, 7, 5, 4, 1, 8, 6 ]
[2, 10, 7, 5, 4, 1, 8 ]
[2, 10, 7, 5, 4, 1 ]
[ 2 , 10, 7, 5 , 4]
[ 10 , 7, 5, 4]
[7, 5, 4]

Total de 5 operaciones de eliminación realizadas. No hay otra secuencia con menos eliminaciones en la que se puedan eliminar el mínimo y el máximo.

Entrada: arr = [56]
Salida: 1
Explicación: Debido a que la array solo tiene una entrada, sirve como el valor mínimo y máximo. Con un solo borrado, podemos eliminarlo.

Entrada: arr = [2, 5, 8, 3, 6, 4]
Salida: 3
Explicación: El elemento mínimo es 2 y el elemento máximo es 8. Podemos visualizar las operaciones de eliminación de la siguiente manera:
[ 2 , 5, 8, 3, 6, 4]
[ 5 , 8, 3, 6, 4]
[ 8 , 3, 6, 4]
[3, 6, 4]

Se realizan un total de 3 eliminaciones. Es el mínimo número posible de eliminaciones.

Enfoque: El problema anterior se puede resolver utilizando la siguiente observación:

Suponga que los elementos max y min existen en el índice i y j, o viceversa, como se muestra a continuación: 

[ _ _ _ _ _ min/max _ _ _ _ _ _ max/min _ _ _ _ _ _ ]
  <-- a -->   (i)   <---  b --->  (j)  <---- c ---->
<-----------------------N ------------------------->

dónde,

• i, j : índice del elemento máximo o mínimo de la array
• a : distancia del elemento mínimo (o máximo) desde el inicio
• b : distancia entre elemento mínimo y máximo
• c : distancia entre el elemento máximo (o mínimo) desde el final
• N : longitud de la array

Ahora veamos las diferentes formas posibles de eliminación:

• Para eliminar uno desde el principio y el otro desde el final :

No. de borrado = (a + c) = ( (i + 1) + (n – j) )

• Para eliminar ambos del inicio de la array:

No. de eliminación = (a + b) = (j + 1)

• Para eliminar ambos del final de la array:

No. de borrado = (b + c) = (n – i)

Usando las ecuaciones anteriores, ahora podemos obtener distancias fácilmente usando el índice de elemento mínimo y máximo. La respuesta es mínimo de estos 3 casos

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return
// the minimum number of deletions
int minDeletions(vector<int>& nums)
{
    int n = nums.size();
 
    // Index of minimum element
    int minindex
      = min_element(nums.begin(), nums.end())
                   - nums.begin();
 
    // Index of maximum element
    int maxindex
      = max_element(nums.begin(), nums.end())
                   - nums.begin();
 
    // Assume that minimum element
    // always occur before maximum element.
    // If not, then swap its index.
    if (minindex > maxindex)
        swap(minindex, maxindex);
 
    // Deletion operations for case-1
    int bothend = (minindex + 1) +
      (n - maxindex);
 
    // Deletion operations for case-2
    int frontend = (maxindex + 1);
 
    // Deletion operations for case-3
    int backend = (n - minindex);
 
    // Least number of deletions is the answer
    int ans = min(bothend,
                  min(frontend, backend));
 
    return ans;
}
 
// Driver code
int main()
{
    vector<int> arr{ 2, 10, 7, 5, 4, 1, 8, 6 };
    cout << minDeletions(arr) << endl;
 
    vector<int> arr2{ 56 };
    cout << minDeletions(arr2);
 
    return 0;
}

// Java code to implement the above approach
import java.util.Arrays;
import java.util.stream.IntStream;
 
class GFG{
 
// Function to return the
// minimum number of deletions
int minDeletions(int[] nums)
{
    int n = nums.length;
     
    // Index of minimum element
    int minindex = findIndex(nums,
    Arrays.stream(nums).min().getAsInt());
 
    // Index of maximum element
    int maxindex = findIndex(
        nums, Arrays.stream(nums).max().getAsInt());
 
    // Assume that minimum element
    // always occur before maximum element.
    // If not, then swap its index.
    if (minindex > maxindex)
    {
        minindex = minindex + maxindex;
        maxindex = minindex - maxindex;
        minindex = minindex - maxindex;
    }
 
    // Deletion operations for case-1
    int bothend = (minindex + 1) + (n - maxindex);
 
    // Deletion operations for case-2
    int frontend = (maxindex + 1);
 
    // Deletion operations for case-3
    int backend = (n - minindex);
 
    // Least number of deletions is the answer
    int ans = Math.min(
        bothend, Math.min(frontend, backend));
 
    return ans;
}
 
// Function to find the index of an element
public static int findIndex(int arr[], int t)
{
    int len = arr.length;
    return IntStream.range(0, len)
        .filter(i -> t == arr[i])
        .findFirst() // first occurrence
        .orElse(-1); // No element found
}
 
// Driver code
public static void main(String[] args)
{
    int[] arr = { 2, 10, 7, 5, 4, 1, 8, 6 };
    System.out.print(new GFG().minDeletions(arr) + "\n");
 
    int []arr2 = { 56 };
    System.out.print(new GFG().minDeletions(arr2));
}
}
 
// This code is contributed by 29AjayKumar

# Python 3 code to implement the above approach
 
# Function to return
# the minimum number of deletions
def minDeletions(nums):
 
    n = len(nums)
 
    # Index of minimum element
    minindex = nums.index(min(nums))
 
    # Index of maximum element
    maxindex = nums.index(max(nums))
 
    # Assume that minimum element
    # always occur before maximum element.
    # If not, then swap its index.
    if (minindex > maxindex):
        minindex, maxindex = maxindex, minindex
 
    # Deletion operations for case-1
    bothend = (minindex + 1) + (n - maxindex)
 
    # Deletion operations for case-2
    frontend = (maxindex + 1)
 
    # Deletion operations for case-3
    backend = (n - minindex)
 
    # Least number of deletions is the answer
    ans = min(bothend,
              min(frontend, backend))
 
    return ans
 
# Driver code
if __name__ == "__main__":
 
    arr = [2, 10, 7, 5, 4, 1, 8, 6]
    print(minDeletions(arr))
 
    arr2 = [56]
    print(minDeletions(arr2))
 
    # This code is contributed by ukasp.

// C# code to implement the above approach
using System;
using System.Linq;
 
public class GFG{
 
// Function to return the
// minimum number of deletions
int minDeletions(int[] nums)
{
    int n = nums.Length;
     
    // Index of minimum element
    int minindex = findIndex(nums,
    nums.Min());
 
    // Index of maximum element
    int maxindex = findIndex(
        nums, nums.Max());
 
    // Assume that minimum element
    // always occur before maximum element.
    // If not, then swap its index.
    if (minindex > maxindex)
    {
        minindex = minindex + maxindex;
        maxindex = minindex - maxindex;
        minindex = minindex - maxindex;
    }
 
    // Deletion operations for case-1
    int bothend = (minindex + 1) + (n - maxindex);
 
    // Deletion operations for case-2
    int frontend = (maxindex + 1);
 
    // Deletion operations for case-3
    int backend = (n - minindex);
 
    // Least number of deletions is the answer
    int ans = Math.Min(
        bothend, Math.Min(frontend, backend));
 
    return ans;
}
 
// Function to find the index of an element
public static int findIndex(int []arr, int t)
{
    int len = arr.Length;
    return  Array.IndexOf(arr, t);
}
 
// Driver code
public static void Main(String[] args)
{
    int[] arr = { 2, 10, 7, 5, 4, 1, 8, 6 };
    Console.Write(new GFG().minDeletions(arr) + "\n");
 
    int []arr2 = { 56 };
    Console.Write(new GFG().minDeletions(arr2));
}
}
 
// This code is contributed by 29AjayKumar

<script>
    // JavaScript code to implement the above approach
 
    // Function to return
    // the minimum number of deletions
    const minDeletions = (nums) => {
        let n = nums.length;
 
        // Index of minimum element
        let minindex = nums.indexOf(Math.min(...nums));
 
        // Index of maximum element
        let maxindex = nums.indexOf(Math.max(...nums));
 
 
        // Assume that minimum element
        // always occur before maximum element.
        // If not, then swap its index.
        if (minindex > maxindex) {
            let temp = minindex;
            minindex = maxindex;
            maxindex = temp;
        }
 
        // Deletion operations for case-1
        let bothend = (minindex + 1) + (n - maxindex);
 
        // Deletion operations for case-2
        let frontend = (maxindex + 1);
 
        // Deletion operations for case-3
        let backend = (n - minindex);
 
        // Least number of deletions is the answer
        let ans = Math.min(bothend, Math.min(frontend, backend));
 
        return ans;
    }
 
    // Driver code
    let arr = [2, 10, 7, 5, 4, 1, 8, 6];
    document.write(`${minDeletions(arr)}<br/>`);
 
    let arr2 = [56];
    document.write(minDeletions(arr2));
 
    // This code is contributed by rakeshsahni
 
</script>

5
1

Complejidad temporal: O(N)
Espacio auxiliar: O(1)