Tamaño del subarreglo más pequeño que se eliminará para contar los elementos del arreglo mayores y menores que K igual

Dado un entero K y una array arr[] que consta de N enteros, la tarea es encontrar la longitud del subarreglo de longitud más pequeña posible que se eliminará de modo que la cantidad de elementos de la array menores y mayores que K en la array restante sea igual.

Ejemplos:

Entrada: arr[] = {5, 7, 2, 8, 7, 4, 5, 9}, K = 5 Salida:
2 Explicación
:
El subarreglo más pequeño que se requiere eliminar es {8, 7}, para hacer el resultante más grande array {5, 7, 2, 4, 5, 9} satisface la condición dada.

Entrada: arr[] = {12, 16, 12, 13, 10}, K = 13
Salida: 3
Explicación:
el subarreglo más pequeño que se requiere eliminar es {12, 13, 10} para hacer el arreglo resultante más grande {12, 16 } satisface la condición dada.

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos posibles y recorrer el resto del arreglo para llevar la cuenta de los elementos del arreglo que son estrictamente mayores y menores que el entero K. Luego, seleccione el subarreglo más pequeño cuya eliminación dé como resultado un arreglo que tenga el mismo número de elementos más pequeños y más grandes.

Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )

Enfoque eficiente: la idea es usar Hashing con alguna modificación en la array para resolverlo en tiempo O (N) . La array dada puede tener 3 tipos de elementos:

  • elemento = K : cambiar elemento a 0 (porque necesitamos elementos que sean estrictamente mayores que K o menores que K )
  • elemento > K : cambiar elemento a 1
  • elemento < K : cambiar elemento a -1

Ahora, calcule la suma de todos los elementos de la array y guárdela en una variable, digamos total_sum . Ahora, total_sum puede tener tres posibles rangos de valores:

  • Si total_sum = 0 : todos los 1 se cancelan con -1. Entonces, el mismo número de elementos mayores y menores que K ya están presentes. No se requiere ninguna operación de eliminación. Por lo tanto, imprima 0 como la respuesta requerida.
  • Si suma_total > 0 : algunos 1 se dejan sin cancelar por -1. es decir , la array tiene más elementos mayores que K y menos elementos menores que K. Por lo tanto, encuentre el subarreglo más pequeño de sum = total_sum , ya que es el subarreglo más pequeño que se eliminará.
  • Si suma_total < 0: algunos -1 se dejan sin cancelar por 1. es decir, la array tiene más cantidad de elementos más pequeños que k y menos cantidad de elementos más grandes que K. Por lo tanto, encuentre el subarreglo más pequeño de sum = total_sum , ya que es el subarreglo más pequeño que se eliminará.

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

C++

// C++ Program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function ot find the length
// of the smallest subarray
int smallSubarray(int arr[], int n,
                  int total_sum)
{
    // Stores (prefix Sum, index)
    // as (key, value) mappings
    unordered_map<int, int> m;
    int length = INT_MAX;
    int prefixSum = 0;
 
    // Iterate till N
    for (int i = 0; i < n; i++) {
 
        // Update the prefixSum
        prefixSum += arr[i];
 
        // Update the length
        if (prefixSum == total_sum) {
            length = min(length, i + 1);
        }
 
        // Put the latest index to
        // find the minimum length
        m[prefixSum] = i;
 
        if (m.count(prefixSum - total_sum)) {
 
            // Update the length
            length
                = min(length,
                      i - m[prefixSum - total_sum]);
        }
    }
 
    // Return the answer
    return length;
}
 
// Function to find the length of
// the largest subarray
int smallestSubarrayremoved(int arr[], int n,
                            int k)
{
 
    // Stores the sum of all array
    // elements after modification
    int total_sum = 0;
 
    for (int i = 0; i < n; i++) {
 
        // Change greater than k to 1
        if (arr[i] > k) {
            arr[i] = 1;
        }
 
        // Change smaller than k to -1
        else if (arr[i] < k) {
            arr[i] = -1;
        }
 
        // Change equal to k to 0
        else {
            arr[i] = 0;
        }
 
        // Update total_sum
        total_sum += arr[i];
    }
 
    // No deletion required, return 0
    if (total_sum == 0) {
        return 0;
    }
 
    else {
 
        // Delete smallest subarray
        // that has sum = total_sum
        return smallSubarray(arr, n,
                             total_sum);
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 12, 16, 12, 13, 10 };
    int K = 13;
 
    int n = sizeof(arr) / sizeof(int);
 
    cout << smallestSubarrayremoved(
        arr, n, K);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
     
// Function ot find the length
// of the smallest subarray
static int smallSubarray(int arr[], int n,
                         int total_sum)
{
     
    // Stores (prefix Sum, index)
    // as (key, value) mappings
    Map<Integer,
        Integer> m = new HashMap<Integer,
                                 Integer>();
                                  
    int length = Integer.MAX_VALUE;
    int prefixSum = 0;
     
    // Iterate till N
    for(int i = 0; i < n; i++)
    {
         
        // Update the prefixSum
        prefixSum += arr[i];
         
        // Update the length
        if (prefixSum == total_sum)
        {
            length = Math.min(length, i + 1);
        }
         
        // Put the latest index to
        // find the minimum length
        m.put(prefixSum, i);
         
        if (m.containsKey(prefixSum - total_sum))
        {
             
            // Update the length
            length = Math.min(length,
                              i - m.get(prefixSum -
                                        total_sum));
        }
    }
     
    // Return the answer
    return length;
}
 
// Function to find the length of
// the largest subarray
static int smallestSubarrayremoved(int arr[], int n,
                                   int k)
{
     
    // Stores the sum of all array
    // elements after modification
    int total_sum = 0;
     
    for(int i = 0; i < n; i++)
    {
         
        // Change greater than k to 1
        if (arr[i] > k)
        {
            arr[i] = 1;
        }
         
        // Change smaller than k to -1
        else if (arr[i] < k)
        {
            arr[i] = -1;
        }
         
        // Change equal to k to 0
        else
        {
            arr[i] = 0;
        }
         
        // Update total_sum
        total_sum += arr[i];
    }
     
    // No deletion required, return 0
    if (total_sum == 0)
    {
        return 0;
    }
    else
    {
         
        // Delete smallest subarray
        // that has sum = total_sum
        return smallSubarray(arr, n, total_sum);
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 12, 16, 12, 13, 10 };
    int K = 13;
    int n = arr.length;
     
    System.out.println(
        smallestSubarrayremoved(arr, n, K));
}
}
 
// This code is contributed by chitranayal

Python3

# Python3 program to implement
# the above approach
import sys
 
# Function ot find the length
# of the smallest subarray
def smallSubarray(arr, n, total_sum):
 
    # Stores (prefix Sum, index)
    # as (key, value) mappings
    m = {}
    length = sys.maxsize
    prefixSum = 0
 
    # Iterate till N
    for i in range(n):
 
        # Update the prefixSum
        prefixSum += arr[i]
 
        # Update the length
        if(prefixSum == total_sum):
            length = min(length, i + 1)
 
        # Put the latest index to
        # find the minimum length
        m[prefixSum] = i
 
        if((prefixSum - total_sum) in m.keys()):
 
            # Update the length
            length = min(length,
                         i - m[prefixSum - total_sum])
 
    # Return the answer
    return length
 
# Function to find the length of
# the largest subarray
def smallestSubarrayremoved(arr, n, k):
 
    # Stores the sum of all array
    # elements after modification
    total_sum = 0
 
    for i in range(n):
 
        # Change greater than k to 1
        if(arr[i] > k):
            arr[i] = 1
 
        # Change smaller than k to -1
        elif(arr[i] < k):
            arr[i] = -1
 
        # Change equal to k to 0
        else:
            arr[i] = 0
 
        # Update total_sum
        total_sum += arr[i]
 
    # No deletion required, return 0
    if(total_sum == 0):
        return 0
    else:
         
        # Delete smallest subarray
        # that has sum = total_sum
        return smallSubarray(arr, n,
                             total_sum)
                              
# Driver Code
arr = [ 12, 16, 12, 13, 10 ]
K = 13
 
n = len(arr)
 
# Function call
print(smallestSubarrayremoved(arr, n, K))
 
# This code is contributed by Shivam Singh

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
     
// Function ot find the length
// of the smallest subarray
static int smallSubarray(int []arr, int n,
                         int total_sum)
{
     
    // Stores (prefix Sum, index)
    // as (key, value) mappings
    Dictionary<int,
               int> m = new Dictionary<int,
                                       int>();
                                  
    int length = int.MaxValue;
    int prefixSum = 0;
     
    // Iterate till N
    for(int i = 0; i < n; i++)
    {
         
        // Update the prefixSum
        prefixSum += arr[i];
         
        // Update the length
        if (prefixSum == total_sum)
        {
            length = Math.Min(length, i + 1);
        }
         
        // Put the latest index to
        // find the minimum length
        if (m.ContainsKey(prefixSum))
            m[prefixSum] = i;
        else
            m.Add(prefixSum, i);
         
        if (m.ContainsKey(prefixSum - total_sum))
        {
             
            // Update the length
            length = Math.Min(length,
                              i - m[prefixSum -
                                    total_sum]);
        }
    }
     
    // Return the answer
    return length;
}
 
// Function to find the length of
// the largest subarray
static int smallestSubarrayremoved(int []arr,
                                   int n, int k)
{
     
    // Stores the sum of all array
    // elements after modification
    int total_sum = 0;
     
    for(int i = 0; i < n; i++)
    {
         
        // Change greater than k to 1
        if (arr[i] > k)
        {
            arr[i] = 1;
        }
         
        // Change smaller than k to -1
        else if (arr[i] < k)
        {
            arr[i] = -1;
        }
         
        // Change equal to k to 0
        else
        {
            arr[i] = 0;
        }
         
        // Update total_sum
        total_sum += arr[i];
    }
     
    // No deletion required, return 0
    if (total_sum == 0)
    {
        return 0;
    }
    else
    {
         
        // Delete smallest subarray
        // that has sum = total_sum
        return smallSubarray(arr, n, total_sum);
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 12, 16, 12, 13, 10 };
    int K = 13;
    int n = arr.Length;
     
    Console.WriteLine(
            smallestSubarrayremoved(arr, n, K));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
// Javascript program to implement
// the above approach
 
// Function ot find the length
// of the smallest subarray
function smallSubarray(arr,n,total_sum)
{
    // Stores (prefix Sum, index)
    // as (key, value) mappings
    let m = new Map();
                                   
    let length = Number.MAX_VALUE;
    let prefixSum = 0;
      
    // Iterate till N
    for(let i = 0; i < n; i++)
    {
          
        // Update the prefixSum
        prefixSum += arr[i];
          
        // Update the length
        if (prefixSum == total_sum)
        {
            length = Math.min(length, i + 1);
        }
          
        // Put the latest index to
        // find the minimum length
        m.set(prefixSum, i);
          
        if (m.has(prefixSum - total_sum))
        {
              
            // Update the length
            length = Math.min(length,
                              i - m.get(prefixSum -
                                        total_sum));
        }
    }
      
    // Return the answer
    return length;
}
 
// Function to find the length of
// the largest subarray
function smallestSubarrayremoved(arr,n,k)
{
    // Stores the sum of all array
    // elements after modification
    let total_sum = 0;
      
    for(let i = 0; i < n; i++)
    {
          
        // Change greater than k to 1
        if (arr[i] > k)
        {
            arr[i] = 1;
        }
          
        // Change smaller than k to -1
        else if (arr[i] < k)
        {
            arr[i] = -1;
        }
          
        // Change equal to k to 0
        else
        {
            arr[i] = 0;
        }
          
        // Update total_sum
        total_sum += arr[i];
    }
      
    // No deletion required, return 0
    if (total_sum == 0)
    {
        return 0;
    }
    else
    {
          
        // Delete smallest subarray
        // that has sum = total_sum
        return smallSubarray(arr, n, total_sum);
    }
}
 
// Driver Code
let arr=[12, 16, 12, 13, 10];
let K = 13;
let n = arr.length;
document.write(smallestSubarrayremoved(arr, n, K));
 
 
// This code is contributed by avanitrachhadiya2155
</script>
Producción: 

3

 

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

Publicación traducida automáticamente

Artículo escrito por jigyansu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *