Encuentre la subarray de longitud mínima que ha dado una subsecuencia en ella

Dado un arreglo arr[] de N elementos, la tarea es encontrar la longitud del subarreglo más pequeño que tiene la secuencia {0, 1, 2, 3, 4} como subsecuencia.

 
Ejemplos:  

Entrada: arr[] = {0, 1, 2, 3, 4, 2, 0, 3, 4} 
Salida:
El subarreglo requerido es {0, 1, 2, 3, 4} con longitud mínima. 
La array completa también incluye la secuencia 
, pero no tiene una longitud mínima.

Entrada: arr[] = {0, 1, 1, 0, 1, 2, 0, 3, 4} 
Salida: 6

Acercarse: 

  • Mantenga una array pref[] de tamaño 5 (igual al tamaño de la secuencia) donde pref[i] almacena el recuento de i en la array dada hasta ahora.
  • Podemos aumentar la cuenta de preferencia para cualquier número solo si pref[Array[i] – 1] > 0. Esto se debe a que, para tener la secuencia completa como una subsecuencia de la array, todos los elementos anteriores de la array La secuencia debe ocurrir antes que la actual. Además, almacena los índices de estos elementos encontrados hasta el momento.
  • Cada vez que presenciamos 4 , es decir, el posible final de la subsecuencia y pref[3] > 0 implica que hemos encontrado la secuencia en nuestra array. Ahora marque ese índice como el final así como el punto de inicio y para todos los demás números en secuencia del 3 al 0 . Aplique la búsqueda binaria para encontrar el índice más cercano al siguiente elemento de la secuencia, lo que nos dará el tamaño del subarreglo válido actual.
  • La respuesta es el tamaño mínimo de todos los subconjuntos válidos encontrados en el paso anterior.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define MAX_INT 1000000
 
// Function to return the minimum length
// of a sub-array which contains
// {0, 1, 2, 3, 4} as a sub-sequence
int solve(int Array[], int N)
{
    // To store the indices where 0, 1, 2,
    // 3 and 4 are present
    vector<int> pos[5];
 
    // To store if there exist a valid prefix
    // of sequence in array
    int pref[5] = { 0 };
 
    // Base Case
    if (Array[0] == 0) {
        pref[0] = 1;
        pos[0].push_back(0);
    }
 
    int ans = MAX_INT;
 
    for (int i = 1; i < N; i++) {
 
        // If current element is 0
        if (Array[i] == 0) {
 
            // Update the count of 0s till now
            pref[0]++;
 
            // Push the index of the new 0
            pos[0].push_back(i);
        }
        else {
 
            // To check if previous element of the
            // given sequence is found till now
            if (pref[Array[i] - 1] > 0) {
                pref[Array[i]]++;
                pos[Array[i]].push_back(i);
 
                // If it is the end of sequence
                if (Array[i] == 4) {
                    int end = i;
                    int start = i;
 
                    // Iterate for other elements of the sequence
                    for (int j = 3; j >= 0; j--) {
                        int s = 0;
                        int e = pos[j].size() - 1;
                        int temp = -1;
 
                        // Binary Search to find closest occurrence
                        // less than equal to starting point
                        while (s <= e) {
                            int m = (s + e) / 2;
                            if (pos[j][m] <= start) {
                                temp = pos[j][m];
                                s = m + 1;
                            }
                            else {
                                e = m - 1;
                            }
                        }
 
                        // Update the starting point
                        start = temp;
                    }
 
                    ans = min(ans, end - start + 1);
                }
            }
        }
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int Array[] = { 0, 1, 2, 3, 4, 2, 0, 3, 4 };
    int N = sizeof(Array) / sizeof(Array[0]);
 
    cout << solve(Array, N);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG
{
static int MAX_INT = 1000000;
 
// Function to return the minimum length
// of a sub-array which contains
// {0, 1, 2, 3, 4} as a sub-sequence
static int solve(int[] array, int N)
{
 
    // To store the indices where 0, 1, 2,
    // 3 and 4 are present
    int[][] pos = new int[5][10000];
 
    // To store if there exist a valid prefix
    // of sequence in array
    int[] pref = new int[5];
 
    // Base Case
    if (array[0] == 0)
    {
        pref[0] = 1;
        pos[0][pos[0].length - 1] = 0;
    }
 
    int ans = MAX_INT;
 
    for (int i = 1; i < N; i++)
    {
 
        // If current element is 0
        if (array[i] == 0)
        {
 
            // Update the count of 0s till now
            pref[0]++;
 
            // Push the index of the new 0
            pos[0][pos[0].length - 1] = i;
        }
         
        else
        {
 
            // To check if previous element of the
            // given sequence is found till now
            if (pref[array[i] - 1] > 0)
            {
                pref[array[i]]++;
                pos[array[i]][pos[array[i]].length - 1] = i;
 
                // If it is the end of sequence
                if (array[i] == 4)
                {
                    int end = i;
                    int start = i;
 
                    // Iterate for other elements of the sequence
                    for (int j = 3; j >= 0; j--)
                    {
                        int s = 0;
                        int e = pos[j].length - 1;
                        int temp = -1;
 
                        // Binary Search to find closest occurrence
                        // less than equal to starting point
                        while (s <= e)
                        {
                            int m = (s + e) / 2;
                            if (pos[j][m] <= start)
                            {
                                temp = pos[j][m];
                                s = m + 1;
                            }
                            else
                                e = m - 1;
                        }
 
                        // Update the starting point
                        start = temp;
                    }
                    ans = Math.min(ans, end - start + 1);
                }
            }
        }
    }
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int[] array = { 0, 1, 2, 3, 4, 2, 0, 3, 4 };
    int N = array.length;
 
    System.out.println(solve(array, N));
}
}
 
// This code is contributed by
// sanjeev2552

Python3

# Python3 implementation of the approach
 
MAX_INT=1000000
 
# Function to return the minimum length
# of a sub-array which contains
# 0, 1, 2, 3, 4 as a sub-sequence
def solve(Array, N):
 
    # To store the indices where 0, 1, 2,
    # 3 and 4 are present
    pos=[[] for i in range(5)]
 
    # To store if there exist a valid prefix
    # of sequence in array
    pref=[0 for i in range(5)]
 
    # Base Case
    if (Array[0] == 0):
        pref[0] = 1
        pos[0].append(0)
     
 
    ans = MAX_INT
 
    for i in range(N):
 
        # If current element is 0
        if (Array[i] == 0):
 
            # Update the count of 0s till now
            pref[0]+=1
 
            # Push the index of the new 0
            pos[0].append(i)
         
        else :
 
            # To check if previous element of the
            # given sequence is found till now
            if (pref[Array[i] - 1] > 0):
                pref[Array[i]]+=1
                pos[Array[i]].append(i)
 
                # If it is the end of sequence
                if (Array[i] == 4) :
                    end = i
                    start = i
 
                    # Iterate for other elements of the sequence
                    for j in range(3,-1,-1):
                        s = 0
                        e = len(pos[j]) - 1
                        temp = -1
 
                        # Binary Search to find closest occurrence
                        # less than equal to starting point
                        while (s <= e):
                            m = (s + e) // 2
                            if (pos[j][m] <= start) :
                                temp = pos[j][m]
                                s = m + 1
                             
                            else :
                                e = m - 1
                             
                         
 
                        # Update the starting point
                        start = temp
                     
 
                    ans = min(ans, end - start + 1)
                 
             
         
     
 
    return ans
 
# Driver code
 
Array = [ 0, 1, 2, 3, 4, 2, 0, 3, 4]
N = len(Array)
 
print(solve(Array, N))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the approach
using System;
 
class GFG
{
static int MAX_INT = 1000000;
  
// Function to return the minimum length
// of a sub-array which contains
// {0, 1, 2, 3, 4} as a sub-sequence
static int solve(int[] array, int N)
{
  
    // To store the indices where 0, 1, 2,
    // 3 and 4 are present
    int[,] pos = new int[5,10000];
  
    // To store if there exist a valid prefix
    // of sequence in array
    int[] pref = new int[5];
  
    // Base Case
    if (array[0] == 0)
    {
        pref[0] = 1;
        pos[0,pos.GetLength(0)- 1] = 0;
    }
  
    int ans = MAX_INT;
  
    for (int i = 1; i < N; i++)
    {
  
        // If current element is 0
        if (array[i] == 0)
        {
  
            // Update the count of 0s till now
            pref[0]++;
  
            // Push the index of the new 0
            pos[0,pos.GetLength(0) - 1] = i;
        }
          
        else
        {
  
            // To check if previous element of the
            // given sequence is found till now
            if (pref[array[i] - 1] > 0)
            {
                pref[array[i]]++;
                pos[array[i],pos.GetLength(1) - 1] = i;
  
                // If it is the end of sequence
                if (array[i] == 4)
                {
                    int end = i;
                    int start = i;
  
                    // Iterate for other elements of the sequence
                    for (int j = 3; j >= 0; j--)
                    {
                        int s = 0;
                        int e = pos.GetLength(1) - 1;
                        int temp = -1;
  
                        // Binary Search to find closest occurrence
                        // less than equal to starting point
                        while (s <= e)
                        {
                            int m = (s + e) / 2;
                            if (pos[j,m] <= start)
                            {
                                temp = pos[j,m];
                                s = m + 1;
                            }
                            else
                                e = m - 1;
                        }
  
                        // Update the starting point
                        start = temp;
                    }
                    ans = Math.Min(ans, end - start + 1);
                }
            }
        }
    }
    return ans;
}
  
// Driver Code
public static void Main(String[] args)
{
    int[] array = { 0, 1, 2, 3, 4, 2, 0, 3, 4 };
    int N = array.Length;
  
    Console.WriteLine(solve(array, N));
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
// Javascript implementation of the approach
 
let MAX_INT = 1000000;
 
// Function to return the minimum length
// of a sub-array which contains
// {0, 1, 2, 3, 4} as a sub-sequence
function solve(array,N)
{
    // To store the indices where 0, 1, 2,
    // 3 and 4 are present
    let pos = new Array(5);
    for(let i=0;i<5;i++)
    {
        pos[i]=new Array(10000);
        for(let j=0;j<10000;j++)
        {
            pos[i][j]=0;
        }
    }
   
    // To store if there exist a valid prefix
    // of sequence in array
    let pref = new Array(5);
      for(let i=0;i<5;i++)
    {
        pref[i]=0;
    }
     
    // Base Case
    if (array[0] == 0)
    {
        pref[0] = 1;
        pos[0][pos[0].length - 1] = 0;
    }
   
    let ans = MAX_INT;
   
    for (let i = 1; i < N; i++)
    {
   
        // If current element is 0
        if (array[i] == 0)
        {
   
            // Update the count of 0s till now
            pref[0]++;
   
            // Push the index of the new 0
            pos[0][pos[0].length - 1] = i;
        }
           
        else
        {
   
            // To check if previous element of the
            // given sequence is found till now
            if (pref[array[i] - 1] > 0)
            {
                pref[array[i]]++;
                pos[array[i]][pos[array[i]].length - 1] = i;
   
                // If it is the end of sequence
                if (array[i] == 4)
                {
                    let end = i;
                    let start = i;
   
                    // Iterate for other elements of the sequence
                    for (let j = 3; j >= 0; j--)
                    {
                        let s = 0;
                        let e = pos[j].length - 1;
                        let temp = -1;
   
                        // Binary Search to find closest occurrence
                        // less than equal to starting point
                        while (s <= e)
                        {
                            let m = Math.floor((s + e) / 2);
                            if (pos[j][m] <= start)
                            {
                                temp = pos[j][m];
                                s = m + 1;
                            }
                            else
                                e = m - 1;
                        }
   
                        // Update the starting point
                        start = temp;
                    }
                    ans = Math.min(ans, end - start + 1);
                }
            }
        }
    }
    return ans;
}
 
// Driver Code
let array=[0, 1, 2, 3, 4, 2, 0, 3, 4];
let N = array.length;
document.write(solve(array, N));
 
 
// This code is contributed by patel2127
</script>
Producción: 

5

 

Publicación traducida automáticamente

Artículo escrito por krikti 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 *