MEX máximo de todos los subarreglos de longitud K

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>
Producción

3 

Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por doreamon_ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *