Dado un arreglo arr[] de N enteros y un entero K , la tarea es encontrar el mínimo y el máximo de todos los subarreglos de tamaño K.
Ejemplos:
Entrada: arr[] = {2, -2, 3, -9, -5, -8}, K = 4
Salida:
-9 3
-9 3
-9 3
Explicación:
A continuación se muestra el subarreglo de tamaño 4 y mínimo y valor máximo de cada subarreglo:
1. {2, -2, 3, -9}, minValue = -9, maxValue = 3
2. {-2, 3, -9, -5}, minValue = -9, maxValue = 3
3. {3, -9, -5, -8}, valor mínimo = -9, valor máximo = 3Entrada: arr[] = { 5, 4, 3, 2, 1, 6, 3, 5, 4, 2, 1 }, K = 3
Salida:
3 5
2 4
1 3
1 6
1 6
3 6
3 5
2 5
1 4
Acercarse:
- Recorra la array dada hasta K elementos y almacene el recuento de cada elemento en un mapa .
- Después de insertar K elementos, para cada uno de los elementos restantes, haga lo siguiente:
- Aumente la frecuencia del elemento actual arr[i] en 1.
- Disminuya la frecuencia de arr[i – K + 1] en 1 para almacenar la frecuencia del subarreglo actual ( arr[i – K + 1, i] ) de tamaño K .
- Dado que el mapa almacena el par de valores clave en orden ordenado. Por lo tanto, el iterador al comienzo del mapa almacena el elemento mínimo y al final del mapa almacena el elemento máximo. Imprime el elemento mínimo y máximo del subarreglo actual.
- Repita los pasos anteriores para cada subarreglo formado.
A continuación se muestra la implementación del enfoque anterior:
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum and
// maximum element for each subarray
// of size K
int maxSubarray(int arr[], int n, int k)
{
// To store the frequency of element
// for every subarray
map<int, int> Map;
// To count the subarray array size
// while traversing array
int l = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
// Increment till we store the
// frequency of first K element
l++;
// Update the count for current
// element
Map[arr[i]]++;
// If subarray size is K, then
// find the minimum and maximum
// for each subarray
if (l == k) {
// Iterator points to end
// of the Map
auto itMax = Map.end();
itMax--;
// Iterator points to start of
// the Map
auto itMin = Map.begin();
// Print the minimum and maximum
// element of current sub-array
cout << itMin->first << ' '
<< itMax->first << endl;
// Decrement the frequency of
// arr[i - K + 1]
Map[arr[i - k + 1]]--;
// if arr[i - K + 1] is zero
// remove from the map
if (Map[arr[i - k + 1]] == 0) {
Map.erase(arr[i - k + 1]);
}
l--;
}
}
return 0;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 5, 4, 3, 2, 1, 6,
3, 5, 4, 2, 1 };
// Subarray size
int k = 3;
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
maxSubarray(arr, n, k);
return 0;
}
3 5 2 4 1 3 1 6 1 6 3 6 3 5 2 5 1 4
Complejidad de tiempo: O(N*log K) , donde N es el número de elemento.
Espacio auxiliar: O(K) , donde K es el tamaño del subarreglo.
Publicación traducida automáticamente
Artículo escrito por adarsh_sinhg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA