Dada una array arr[] que consta de N enteros, la tarea es encontrar la longitud del subarreglo más pequeño que se requiere eliminar para que los elementos restantes de la array sean consecutivos .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 7, 5, 4, 5}
Salida: 2
Explicación:
Eliminar el subarreglo {7, 5} del arreglo arr[] modifica el arreglo a {1, 2, 3 , 4, 5}, lo que hace que todos los elementos de la array sean consecutivos. Por lo tanto, la longitud del subarreglo eliminado es 2, que es el mínimo.Entrada: arr[] = {4, 5, 6, 8, 9, 10}
Salida: 3
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es eliminar generar todos los subarreglos posibles del arreglo arr[] y, para cada uno de ellos, verificar si su eliminación hace que los elementos restantes del arreglo sean consecutivos o no. Después de verificar todos los subarreglos, imprima la longitud del subarreglo mínimo obtenido que satisface la condición.
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar almacenando la longitud del prefijo y el sufijo más largos de los elementos consecutivos y luego encontrar la longitud mínima del subarreglo que se debe eliminar de modo que la concatenación del prefijo y el sufijo forme una secuencia de elementos consecutivos. .
Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos L como 0 y R como (N – 1) para almacenar los índices finales del prefijo más largo y el índice inicial del sufijo más largo de elementos consecutivos, respectivamente.
- Actualice el valor de L al primer índice donde arr[i] + 1 no es igual a arr[i + 1] de modo que arr[0, …, L] sea una array de prefijos consecutivos.
- Actualice el valor de R al primer índice desde el final donde arr[i] no es igual a arr[i – 1] + 1 de modo que arr[R, …, N – 1] sea una array de sufijos consecutivos.
- Inicialice una variable, digamos ans, para almacenar el mínimo de (N – L – 1) y R para almacenar el resultado requerido.
- Si el valor de arr[R] ≤ arr[L] + 1 , almacene el índice correcto, R1 como arr[0, …, L, R1, …, N – 1] es una array consecutiva.
- Si el valor de (R1 – L – 1) es menor que el valor de ans , actualice el valor de ans a (R1 – L – 1) .
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the length of the
// smallest subarray to be removed to
// make remaining array elements consecutive
void shortestSubarray(int* A, int N)
{
int i;
// Store the ending index of the
// longest prefix consecutive array
int left_index;
// Traverse the array to find the
// longest prefix consecutive sequence
for (i = 0; i < N - 1; i++) {
if (A[i] + 1 != A[i + 1])
break;
}
// A[0...left_index] is the
// prefix consecutive sequence
left_index = i;
// Store the starting index of the
// longest suffix consecutive sequence
int right_index;
// Traverse the array to find the
// longest suffix consecutive sequence
for (i = N - 1; i >= 1; i--) {
if (A[i] != A[i - 1] + 1)
break;
}
// A[right_index...N-1] is
// the consecutive sequence
right_index = i;
int updated_right;
// Store the smallest subarray
// required to be removed
int minLength = min(N - left_index - 1,
right_index);
// Check if subarray from the
// middle can be removed
if (A[right_index]
<= A[left_index] + 1) {
// Update the right index s.t.
// A[0, N-1] is consecutive
updated_right = right_index
+ A[left_index]
- A[right_index] + 1;
// If updated_right < N, then
// update the minimumLength
if (updated_right < N)
minLength = min(minLength,
updated_right
- left_index - 1);
}
// Print the required result
cout << minLength;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 7, 4, 3, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
shortestSubarray(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to find the length of the
// smallest subarray to be removed to
// make remaining array elements consecutive
static void shortestSubarray(int A[], int N)
{
int i;
// Store the ending index of the
// longest prefix consecutive array
int left_index;
// Traverse the array to find the
// longest prefix consecutive sequence
for(i = 0; i < N - 1; i++)
{
if (A[i] + 1 != A[i + 1])
break;
}
// A[0...left_index] is the
// prefix consecutive sequence
left_index = i;
// Store the starting index of the
// longest suffix consecutive sequence
int right_index;
// Traverse the array to find the
// longest suffix consecutive sequence
for(i = N - 1; i >= 1; i--)
{
if (A[i] != A[i - 1] + 1)
break;
}
// A[right_index...N-1] is
// the consecutive sequence
right_index = i;
int updated_right;
// Store the smallest subarray
// required to be removed
int minLength = Math.min(N - left_index - 1,
right_index);
// Check if subarray from the
// middle can be removed
if (A[right_index] <= A[left_index] + 1)
{
// Update the right index s.t.
// A[0, N-1] is consecutive
updated_right = right_index + A[left_index] -
A[right_index] + 1;
// If updated_right < N, then
// update the minimumLength
if (updated_right < N)
minLength = Math.min(minLength,
updated_right -
left_index - 1);
}
// Print the required result
System.out.println(minLength);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 7, 4, 3, 5 };
int N = arr.length;
shortestSubarray(arr, N);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach # Function to find the length of the # smallest subarray to be removed to # make remaining array elements consecutive def shortestSubarray(A, N): i = 0 # Store the ending index of the # longest prefix consecutive array left_index = 0 # Traverse the array to find the # longest prefix consecutive sequence for i in range(N - 1): if (A[i] + 1 != A[i + 1]): break # A[0...left_index] is the # prefix consecutive sequence left_index = i # Store the starting index of the # longest suffix consecutive sequence right_index = 0 # Traverse the array to find the # longest suffix consecutive sequence i = N - 1 while (i >= 1): if (A[i] != A[i - 1] + 1): break i -= 1 # A[right_index...N-1] is # the consecutive sequence right_index = i updated_right = 0 # Store the smallest subarray # required to be removed minLength = min(N - left_index - 1, right_index) # Check if subarray from the # middle can be removed if (A[right_index] <= A[left_index] + 1): # Update the right index s.t. # A[0, N-1] is consecutive updated_right = (right_index + A[left_index] - A[right_index] + 1) # If updated_right < N, then # update the minimumLength if (updated_right < N): minLength = min(minLength, updated_right - left_index - 1) # Print the required result print(minLength) # Driver Code if __name__ == '__main__': arr = [ 1, 2, 3, 7, 4, 3, 5 ] N = len(arr) shortestSubarray(arr, N) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the length of the
// smallest subarray to be removed to
// make remaining array elements consecutive
static void shortestSubarray(int[] A, int N)
{
int i;
// Store the ending index of the
// longest prefix consecutive array
int left_index;
// Traverse the array to find the
// longest prefix consecutive sequence
for(i = 0; i < N - 1; i++)
{
if (A[i] + 1 != A[i + 1])
break;
}
// A[0...left_index] is the
// prefix consecutive sequence
left_index = i;
// Store the starting index of the
// longest suffix consecutive sequence
int right_index;
// Traverse the array to find the
// longest suffix consecutive sequence
for(i = N - 1; i >= 1; i--)
{
if (A[i] != A[i - 1] + 1)
break;
}
// A[right_index...N-1] is
// the consecutive sequence
right_index = i;
int updated_right;
// Store the smallest subarray
// required to be removed
int minLength = Math.Min(N - left_index - 1,
right_index);
// Check if subarray from the
// middle can be removed
if (A[right_index] <= A[left_index] + 1)
{
// Update the right index s.t.
// A[0, N-1] is consecutive
updated_right = right_index + A[left_index] -
A[right_index] + 1;
// If updated_right < N, then
// update the minimumLength
if (updated_right < N)
minLength = Math.Min(minLength,
updated_right -
left_index - 1);
}
// Print the required result
Console.WriteLine(minLength);
}
// Driver code
static public void Main()
{
int[] arr = { 1, 2, 3, 7, 4, 3, 5 };
int N = arr.Length;
shortestSubarray(arr, N);
}
}
// This code is contributed by offbeat
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the length of the
// smallest subarray to be removed to
// make remaining array elements consecutive
function shortestSubarray(A, N)
{
let i;
// Store the ending index of the
// longest prefix consecutive array
let left_index;
// Traverse the array to find the
// longest prefix consecutive sequence
for(i = 0; i < N - 1; i++)
{
if (A[i] + 1 != A[i + 1])
break;
}
// A[0...left_index] is the
// prefix consecutive sequence
left_index = i;
// Store the starting index of the
// longest suffix consecutive sequence
let right_index;
// Traverse the array to find the
// longest suffix consecutive sequence
for(i = N - 1; i >= 1; i--)
{
if (A[i] != A[i - 1] + 1)
break;
}
// A[right_index...N-1] is
// the consecutive sequence
right_index = i;
let updated_right;
// Store the smallest subarray
// required to be removed
let minLength = Math.min(N - left_index - 1,
right_index);
// Check if subarray from the
// middle can be removed
if (A[right_index] <= A[left_index] + 1)
{
// Update the right index s.t.
// A[0, N-1] is consecutive
updated_right = right_index + A[left_index] -
A[right_index] + 1;
// If updated_right < N, then
// update the minimumLength
if (updated_right < N)
minLength = Math.min(minLength,
updated_right -
left_index - 1);
}
// Print the required result
document.write(minLength);
}
// Driver code
let arr = [ 1, 2, 3, 7, 4, 3, 5 ];
let N = arr.length;
shortestSubarray(arr, N);
// This code is contributed by susmitakundugoaldanga.
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ManikantaBandla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA