Dado un arreglo de enteros arr[] de tamaño N y un entero X , la tarea es encontrar el subarreglo más largo donde la diferencia absoluta entre dos elementos no sea mayor que X .
Ejemplos:
Entrada: arr = { 8, 4, 2, 6, 7 }, X = 4
Salida: 4 2 6
Explicación:
El subarreglo descrito por el índice [1, 3], es decir, { 4, 2, 6 } no contiene tal diferencia de dos elementos que es mayor que 4.
Entrada: arr = { 15, 10, 1, 2, 4, 7, 2}, X = 5
Salida: 2 4 7 2
Explicación:
El subarreglo descrito por índices [ 3, 6], es decir, { 2, 4, 7, 2 } no contiene tal diferencia de dos elementos que sea mayor que 5.
Enfoque ingenuo: la solución simple es considerar todos los subarreglos uno por uno, encontrar el elemento máximo y mínimo de ese subarreglo y verificar si su diferencia no es mayor que X . Entre todos estos subconjuntos, imprima el subconjunto más largo.
Complejidad de tiempo: O(N 3 )
Enfoque eficiente: La idea es utilizar la técnica de ventana deslizante para considerar un subconjunto y utilizar una estructura de datos de mapa para encontrar el elemento máximo y mínimo en ese subconjunto.
- Al principio, el Inicio y el Fin de la ventana apuntan al índice 0-ésimo .
- En cada iteración, el elemento en Fin se inserta en el Mapa si aún no está presente o, de lo contrario, se incrementa su recuento.
- Si la diferencia entre el elemento máximo y mínimo no es mayor que X , actualice la longitud máxima del subarreglo requerido y almacene el comienzo de ese subarreglo en una variable.
- De lo contrario, incremente el Inicio de la ventana hasta que la diferencia entre el elemento máximo y mínimo no sea mayor que X .
- Al incrementar el Inicio , el tamaño de la ventana disminuye, elimine el elemento en el Inicio del Mapa si y solo si el recuento de ese elemento se vuelve cero.
Finalmente, imprima el subarreglo con la longitud más larga y la diferencia absoluta entre dos elementos no sea mayor que X .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the longest sub-array
// where the absolute difference between any
// two elements is not greater than X
#include <bits/stdc++.h>
using namespace std;
// Function that prints the longest sub-array
// where the absolute difference between any
// two element is not greater than X
void longestSubarray(int* A, int N, int X)
{
// Initialize a variable to store
// length of longest sub-array
int maxLen = 0;
// Initialize a variable to store the
// beginning of the longest sub-array
int beginning = 0;
// Initialize a map to store the maximum
// and the minimum elements for a given window
map<int, int> window;
// Initialize the window
int start = 0, end = 0;
// Loop through the array
for (; end < N; end++) {
// Increment the count of that
// element in the window
window[A[end]]++;
// Find the maximum and minimum element
// in the current window
auto minimum = window.begin()->first;
auto maximum = window.rbegin()->first;
// If the difference is not
// greater than X
if (maximum - minimum <= X) {
// Update the length of the longest
// sub-array and store the beginning
// of the sub-array
if (maxLen < end - start + 1) {
maxLen = end - start + 1;
beginning = start;
}
}
// Decrease the size of the window
else {
while (start < end) {
// Remove the element at start
window[A[start]]--;
// Remove the element from the window
// if its count is zero
if (window[A[start]] == 0) {
window.erase(window.find(A[start]));
}
// Increment the start of the window
start++;
// Find the maximum and minimum element
// in the current window
auto minimum = window.begin()->first;
auto maximum = window.rbegin()->first;
// Stop decreasing the size of window
// when difference is not greater
if (maximum - minimum <= X)
break;
}
}
}
// Print the longest sub-array
for (int i = beginning; i < beginning + maxLen; i++)
cout << A[i] << " ";
}
// Driver Code
int main()
{
int arr[] = { 15, 10, 1, 2, 4, 7, 2 }, X = 5;
int n = sizeof(arr) / sizeof(arr[0]);
longestSubarray(arr, n, X);
return 0;
}
Java
// JAVA program to find the longest sub-array
// where the absolute difference between any
// two elements is not greater than X
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG
{
// Function that prints the longest sub-array
// where the absolute difference between any
// two element is not greater than X
static void longestSubarray(int A[], int N, int X)
{
// Initialize a variable to store
// length of longest sub-array
int maxLen = 0;
// Initialize a variable to store the
// beginning of the longest sub-array
int beginning = 0;
// Initialize a map to store the maximum
// and the minimum elements for a given window
TreeMap<Integer, Integer> window = new TreeMap<>();
// Initialize the window
int start = 0, end = 0;
// Loop through the array
for (; end < N; end++)
{
// Increment the count of that
// element in the window
window.put(A[end],
window.getOrDefault(A[end], 0) + 1);
// Find the maximum and minimum element
// in the current window
int minimum = window.firstKey();
int maximum = window.lastKey();
// If the difference is not
// greater than X
if (maximum - minimum <= X)
{
// Update the length of the longest
// sub-array and store the beginning
// of the sub-array
if (maxLen < end - start + 1) {
maxLen = end - start + 1;
beginning = start;
}
}
// Decrease the size of the window
else {
while (start < end)
{
// Remove the element at start
window.put(A[start],
window.get(A[start]) - 1);
// Remove the element from the window
// if its count is zero
if (window.get(A[start]) == 0) {
window.remove(A[start]);
}
// Increment the start of the window
start++;
// Find the maximum and minimum element
// in the current window
minimum = window.firstKey();
maximum = window.lastKey();
// Stop decreasing the size of window
// when difference is not greater
if (maximum - minimum <= X)
break;
}
}
}
// Print the longest sub-array
for (int i = beginning; i < beginning + maxLen; i++)
System.out.print(A[i] + " ");
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = { 15, 10, 1, 2, 4, 7, 2 }, X = 5;
// store the size of the array
int n = arr.length;
// Function call
longestSubarray(arr, n, X);
}
}
// This code is contributed by Kingash.
Python3
# Python3 program to find the longest sub-array
# where the absolute difference between any
# two elements is not greater than X
# Function that prints the longest sub-array
# where the absolute difference between any
# two element is not greater than X
def longestSubarray(A, N, X):
# Initialize a variable to store
# length of longest sub-array
maxLen = 0
# Initialize a variable to store the
# beginning of the longest sub-array
beginning = 0
# Initialize a map to store the maximum
# and the minimum elements for a given window
window = {}
# Initialize the window
start = 0
# Loop through the array
for end in range(N):
# Increment the count of that
# element in the window
if A[end] in window:
window[A[end]] += 1
else:
window[A[end]] = 1
# Find the maximum and minimum element
# in the current window
minimum = min(list(window.keys()))
maximum = max(list(window.keys()))
# If the difference is not
# greater than X
if maximum - minimum <= X:
# Update the length of the longest
# sub-array and store the beginning
# of the sub-array
if maxLen < end - start + 1:
maxLen = end - start + 1
beginning = start
# Decrease the size of the window
else:
while start < end:
# Remove the element at start
window[A[start]] -= 1
# Remove the element from the window
# if its count is zero
if window[A[start]] == 0:
window.pop(A[start])
# Increment the start of the window
start += 1
# Find the maximum and minimum element
# in the current window
minimum = min(list(window.keys()))
maximum = max(list(window.keys()))
# Stop decreasing the size of window
# when difference is not greater
if maximum - minimum <= X:
break
# Print the longest sub-array
for i in range(beginning, beginning + maxLen):
print(A[i], end = ' ')
# Driver Code
arr = [15, 10, 1, 2, 4, 7, 2]
X = 5
n = len(arr)
longestSubarray(arr, n, X)
# This code is contributed by Shivam Singh
Javascript
<script>
// JavaScript program to find the longest sub-array
// where the absolute difference between any
// two elements is not greater than X
// Function that prints the longest sub-array
// where the absolute difference between any
// two element is not greater than X
function longestSubarray(A, N, X){
// Initialize a variable to store
// length of longest sub-array
let maxLen = 0
// Initialize a variable to store the
// beginning of the longest sub-array
let beginning = 0
// Initialize a map to store the maximum
// and the minimum elements for a given window
let window = new Map()
// Initialize the window
let start = 0
// Loop through the array
for(let end=0;end<N;end++){
// Increment the count of that
// element in the window
if(window.has(A[end]))
window.set(A[end],window.get(A[end]) + 1)
else
window.set(A[end] , 1)
// Find the maximum and minimum element
// in the current window
let minimum = Math.min(...window.keys())
let maximum = Math.max(...window.keys())
// If the difference is not
// greater than X
if(maximum - minimum <= X){
// Update the length of the longest
// sub-array and store the beginning
// of the sub-array
if(maxLen < end - start + 1){
maxLen = end - start + 1
beginning = start
}
}
// Decrease the size of the window
else{
while(start < end){
// Remove the element at start
window.set(A[start],window.get(A[start]) - 1)
// Remove the element from the window
// if its count is zero
if(window.get(A[start]) == 0)
window.delete(A[start])
// Increment the start of the window
start += 1
// Find the maximum and minimum element
// in the current window
minimum = Math.min(...window.keys())
maximum = Math.max(...window.keys())
// Stop decreasing the size of window
// when difference is not greater
if(maximum - minimum <= X)
break
}
}
}
// Print the longest sub-array
for(let i=beginning;i<beginning+maxLen;i++){
document.write(A[i],' ')
}
}
// Driver Code
let arr = [15, 10, 1, 2, 4, 7, 2]
let X = 5
let n = arr.length
longestSubarray(arr, n, X)
// This code is contributed by Shinjanpatra
</script>
Producción:
2 4 7 2
Complejidad de tiempo: O(N * log(N))
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA