Dada una array arr[] que consta de N enteros distintos y un entero K , la tarea es encontrar el MEX máximo de todos los subarreglos de longitud K .
El MEX es el entero positivo más pequeño que no está presente en la array .
Ejemplos:
Entrada: array[] = {3, 2, 1, 4}, K = 2
Salida: 3
Explicación:
Todos los subarreglos que tienen una longitud de 2 son {3, 2}, {2, 1}, {1, 4}.
En el subarreglo {3, 2}, el entero positivo más pequeño que no está presente es 1.
En el subarreglo {2, 1}, el entero positivo más pequeño que no está presente es 3.
En el subarreglo {1, 4}, el entero positivo más pequeño que no está presente es 2.Entrada: arr[] = {6, 1, 3, 2, 4}, K = 3
Salida: 4
Explicación:
Todos los subarreglos que tienen una longitud de 3 son {6, 1, 3}, {1, 3, 2}, {3 , 2, 4}
En el subarreglo {6, 1, 3}, el entero positivo más pequeño que no está presente es 2.
En el subarreglo {1, 3, 2}, el entero positivo más pequeño que no está presente es 4.
En el subarreglo { 3, 2, 4}, el entero positivo más pequeño que no está presente es 1.
Enfoque ingenuo: el enfoque más simple es generar todos los subarreglos de longitud K y encontrar MEX de cada subarreglo . Después de encontrar todos los MEX , imprima el máximo de los obtenidos.
Complejidad de Tiempo: O(K * N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: Para optimizar el enfoque anterior, la idea es utilizar la estructura de datos Conjunto y Técnica de ventana deslizante . Siga los pasos a continuación para resolver el problema:
- Inicialice un conjunto S para almacenar valores que no están presentes en el subarreglo actual e inicialmente inserte 1 a N + 1 número en él porque inicialmente, el tamaño de la ventana es 0 .
- Recorra el rango [0, K – 1] y borre arr[i] del conjunto, el primer elemento del conjunto es MEX del subarreglo a partir del índice 0 y la longitud K , inicialice una variable mex y almacene este valor en mex .
- Ahora itere de K a N – 1 y borre arr[i] para establecer e insertar arr[i – K] y actualice mex = max(mex, primer elemento del conjunto).
- Después de los pasos anteriores, imprima mex como máximo MEX entre subarreglo con longitud K.
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 return maximum MEX of // all K length subarray void maxMEX(int arr[], int N, int K) { // Stores element from 1 to N + 1 // is nor present in subarray set<int> s; // Store number 1 to N + 1 in set s for (int i = 1; i <= N + 1; i++) s.insert(i); // Find the MEX of K length subarray // starting from index 0 for (int i = 0; i < K; i++) s.erase(arr[i]); int mex = *(s.begin()); // Find the MEX of all subarray of // length K by erasing arr[i] // and inserting arr[i-K] for (int i = K; i < N; i++) { s.erase(arr[i]); s.insert(arr[i - K]); // Store first element of set int firstElem = *(s.begin()); // Updating mex mex = max(mex, firstElem); } // Print maximum MEX of all K // length subarray cout << mex << ' '; } // Driver Code int main() { // Given array int arr[] = { 3, 2, 1, 4 }; // Given length of subarray int K = 2; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Function Call maxMEX(arr, N, K); return 0; }
Java
// Java program for the // above approach import java.util.*; class GFG { // Function to return maximum // MEX of all K length subarray static void maxMEX(int arr[], int N, int k) { // Stores element from // 1 to N + 1 is nor // present in subarray // We need a Tree Set since // we want to store the // elements in ascending // order TreeSet<Integer> s = new TreeSet<>(); // Store number 1 to // N + 1 in set s for(int l=1;l<=N+1;l++) s.add(l); // i and j point to the start of the array // i.e index 0 int i=0; int j=0; int mex = 0; // mex variable which stores the mex for // generated subArrays int maxMex = Integer.MIN_VALUE; //maxMex contains the maximum mex value for all subArrays while(j < N) { if(s.contains(arr[j])) s.remove(arr[j]); int windowSize = j-i+1; // window size at any instant is given by j-i+1; if(windowSize < k) j++; // here, windowSize < k , i.e we haven't reached the first // window of size k yet.. so we increment j; else if(windowSize == k) { //here , windowSize equals k, we are to get an answer everytime // we reached the windowSize of k , first element of the set has // mex for this subArray; mex = s.pollFirst(); // set.pollFirst() function removes the firstElement in the treeset; maxMex = Math.max(maxMex,mex); // before sliding the window , we need to undo the calculations // done at the starting point , i.e i; s.add(arr[i]); i++; j++; // sliding the window by 1 each in i and j , so as to maintain // the windowSize k; } } System.out.println(maxMex); } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 6, 1, 3, 2, 4 }; // Given length of subarray int K = 3; // Size of the array int N = arr.length; // Function Call maxMEX(arr, N, K); } } // This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach # Function to return maximum MEX of # all K length subarray def maxMEX(arr, N, K): # Stores element from 1 to N + 1 # is nor present in subarray s = set() # Store number 1 to N + 1 in set s for i in range(1, N + 2): s.add(i) # Find the MEX of K length subarray # starting from index 0 for i in range(K): s.remove(arr[i]) mex = list(s)[0] # Find the MEX of all subarray of # length K by erasing arr[i] # and inserting arr[i-K] for i in range(K, N): s.remove(arr[i]) s.add(arr[i - K]) # Store first element of set firstElem = list(s)[0] # Updating mex mex = max(mex, firstElem) # Print maximum MEX of all K # length subarray print(mex) # Driver code if __name__ == '__main__': # Given array arr = [3, 2, 1, 4] # Size of the array N = len(arr) # Given length of subarray K = 2 # Function Call maxMEX(arr, N, K) # This code is contributed by Shivam Singh
C#
// C# program for the // above approach using System; using System.Collections.Generic; class GFG { // Function to return maximum // MEX of all K length subarray static void maxMEX(int[] arr, int N, int K) { // Stores element from // 1 to N + 1 is nor // present in subarray HashSet<int> s = new HashSet<int>(); // Store number 1 to // N + 1 in set s for (int i = 1; i <= N + 1; i++) s.Add(i); // Find the MEX of K length // subarray starting from index 0 for (int i = 0; i < K; i++) s.Remove(arr[i]); List<int> v = new List<int>(); foreach(int i in s) { v.Add(i); } int mex = v[0]; // Find the MEX of all subarray of // length K by erasing arr[i] // and inserting arr[i-K] for (int i = K; i < N; i++) { v.Remove(arr[i]); v.Add(arr[i - K]); // Store first element // of set int firstElem = v[0]; // Updating mex mex = Math.Max(mex, firstElem); } // Print maximum MEX of all K // length subarray Console.Write(mex - 2 + " "); } // Driver Code public static void Main(String[] args) { // Given array int[] arr = { 3, 2, 1, 4 }; // Given length of subarray int K = 2; // Size of the array int N = arr.Length; // Function Call maxMEX(arr, N, K); } } // This code is contributed by gauravrajput1
Javascript
<script> // JavaScript program for the above approach // Function to return maximum MEX of // all K length subarray function maxMEX( arr, N, K) { // Stores element from 1 to N + 1 // is nor present in subarray let s = new Set(); // Store number 1 to N + 1 in set s for (let i = 1; i <= N + 1; i++) s.add(i); // Find the MEX of K length subarray // starting from index 0 for (let i = 0; i < K; i++) s.delete(arr[i]); let a = Array.from(s); var mex = a[0]; // Find the MEX of all subarray of // length K by erasing arr[i] // and inserting arr[i-K] for (let i = K; i < N; i++) { s.delete(arr[i]); s.add(arr[i - K]); // Store first element of set let ss = Array.from(s); var firstElem = ss[ss.length-1]; // Updating mex mex = Math.max(mex, firstElem); } // Print maximum MEX of all K // length subarray document.write( mex ,' '); } // Driver Code // Given array let arr = [ 3, 2, 1, 4 ]; // Given length of subarray let K = 2; // Size of the array let N = arr.length; // Function Call maxMEX(arr, N, K); </script>
3
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)