Dado un arreglo arr[] que consta de N enteros positivos distintos y un entero K , la tarea es encontrar el MEX mínimo 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: arr[] = {1, 2, 3}, K = 2
Salida: 1
Explicación:
Todos los subarreglos de longitud 2 son {1, 2}, {2, 3}.
En el subarreglo {1, 2}, el entero positivo más pequeño que no está presente es 3.
En el subarreglo {2, 3}, el entero positivo más pequeño que no está presente es 1.
Por lo tanto, el mínimo de todos los MEX para todos los subarreglos de longitud K (= 2) es 1.Entrada: arr[] = {1, 2, 3, 4, 5, 6}, K = 3
Salida: 1
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos de longitud K y encontrar el MEX para cada subarreglo . Después de encontrar todos los MEX , imprima el mínimo de los obtenidos.
Complejidad de Tiempo: O(K * N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de una técnica de ajuste y ventana deslizante . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos mex , para almacenar el mínimo entre todos los MEX de subarreglos de tamaño K .
- Inicialice un conjunto S para almacenar valores que no están presentes en el subarreglo actual. Inicialmente, inserte todos los números del rango [1, N + 1] en él, porque inicialmente, el tamaño de la ventana es 0 .
- Iterar sobre el rango [0, K – 1] y borrar el elemento arr[i] del conjunto .
- Ahora, el primer elemento del conjunto es MEX del subarreglo sobre el rango [0, K] y almacene este valor en mex .
- Ahora, itere sobre el rango [K, N – 1] y realice los siguientes pasos:
- Inserte el elemento arr[i] en el conjunto .
- Borra el elemento arr[i – K] del conjunto .
- Ahora, el primer elemento del conjunto es el MEX para el subarreglo actual. Por lo tanto, actualice el valor de mex al mínimo de mex y el primer elemento del conjunto .
- Después de completar los pasos anteriores, imprima el valor de mex como el MEX mínimo entre todos los subarreglos de tamaño 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 minimum
// MEX from all K-length subarrays
void minimumMEX(int arr[], int N, int K)
{
// Stores element from [1, N + 1]
// which are not 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 subarrays
// 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 the mex
mex = min(mex, firstElem);
}
// Print minimum MEX of
// all K length subarray
cout << mex << ' ';
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6 };
int K = 3;
int N = sizeof(arr) / sizeof(arr[0]);
minimumMEX(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.HashSet;
class GFG{
// Function to return minimum
// MEX from all K-length subarrays
static void minimumMEX(int arr[], int N, int K)
{
// Stores element from [1, N + 1]
// which are not present in subarray
HashSet<Integer> s = new HashSet<Integer>();
// 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]);
int mex = s.iterator().next();
// Find the MEX of all subarrays
// of length K by erasing arr[i]
// and inserting arr[i - K]
for(int i = K; i < N; i++)
{
s.remove(arr[i]);
s.add(arr[i - K]);
// Store first element of set
int firstElem = s.iterator().next();
// Updating the mex
mex = Math.min(mex, firstElem);
}
// Print minimum MEX of
// all K length subarray
System.out.print(mex + " ");
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5, 6 };
int K = 3;
int N = arr.length;
minimumMEX(arr, N, K);
}
}
// This code is contributed by abhinavjain194
Python3
# Python 3 program for the above approach # Function to return minimum # MEX from all K-length subarrays def minimumMEX(arr, N, K): # Stores element from [1, N + 1] # which are not present in subarray s = set() # Store number 1 to N + 1 in set s for i in range(1, N + 2, 1): 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 subarrays # of length K by erasing arr[i] # and inserting arr[i - K] for i in range(K,N,1): s.remove(arr[i]) s.add(arr[i - K]) # Store first element of set firstElem = list(s)[0] # Updating the mex mex = min(mex, firstElem) # Print minimum MEX of # all K length subarray print(mex) # Driver Code if __name__ == '__main__': arr = [1, 2, 3, 4, 5, 6] K = 3 N = len(arr) minimumMEX(arr, N, K) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG{
// Function to return minimum
// MEX from all K-length subarrays
static void minimumMEX(int[] arr, int N, int K)
{
// Stores element from [1, N + 1]
// which are not 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]);
int mex = s.First();
// Find the MEX of all subarrays
// of length K by erasing arr[i]
// and inserting arr[i - K]
for(int i = K; i < N; i++)
{
s.Remove(arr[i]);
s.Add(arr[i - K]);
// Store first element of set
int firstElem = s.First();
// Updating the mex
mex = Math.Min(mex, firstElem);
}
// Print minimum MEX of
// all K length subarray
Console.Write(mex + " ");
}
// Driver code
static void Main()
{
int[] arr = { 1, 2, 3, 4, 5, 6 };
int K = 3;
int N = arr.Length;
minimumMEX(arr, N, K);
}
}
// This code is contributed by abhinavjain194
Javascript
<script>
// Javascript program for the above approach
// Function to return minimum
// MEX from all K-length subarrays
function minimumMEX(arr, N, K)
{
// Stores element from [1, N + 1]
// which are not 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 entry = s.entries();
let mex = 1;
// Find the MEX of all subarrays
// 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 firstElem = entry.next().value
// Updating the mex
mex = Math.min(mex, 1);
}
// Print minimum MEX of
// all K length subarray
document.write(mex + " ");
}
let arr = [ 1, 2, 3, 4, 5, 6 ];
let K = 3;
let N = arr.length;
minimumMEX(arr, N, K);
// This code is contributed by divyesh072019.
</script>
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar: O(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