Subarreglo más largo que consta de elementos únicos de un Array

Dada una array arr[] que consta de N enteros, la tarea es encontrar el subarreglo más grande que consta solo de elementos únicos.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4, 5, 1, 2, 3} 
Salida:
Explicación: Un subarreglo posible es {1, 2, 3, 4, 5}.

Entrada: arr[]={1, 2, 4, 4, 5, 6, 7, 8, 3, 4, 5, 3, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4 } 
Salida:
Explicación: El único subarreglo posible es {3, 4, 5, 6, 7, 8, 1, 2}.

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos de la array dada y verificar si contiene duplicados o no usar HashSet . Encuentre el subarreglo más largo que satisfaga la condición. 
Complejidad temporal: O(N 3 logN) 
Espacio auxiliar: O(N)

Enfoque eficiente: HashMap puede optimizar el enfoque anterior . Siga los pasos a continuación para resolver el problema:

  1. Inicialice una variable j para almacenar el valor máximo del índice de modo que no haya elementos repetidos entre el índice i y j
  2. Recorra la array y siga actualizando j en función de la aparición anterior de a[i] almacenada en HashMap.
  3. Después de actualizar j , actualice ans en consecuencia para almacenar la longitud máxima del subarreglo deseado.
  4. Print ans , después del recorrido, se completa.

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

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to find largest
// subarray with no duplicates
int largest_subarray(int a[], int n)
{
    // Stores index of array elements
    unordered_map<int, int> index;
    int ans = 0;
    for (int i = 0, j = 0; i < n; i++) {
  
        // Update j based on previous
        // occurrence of a[i]
        j = max(index[a[i]], j);
  
        // Update ans to store maximum
        // length of subarray
        ans = max(ans, i - j + 1);
  
        // Store the index of current
        // occurrence of a[i]
        index[a[i]] = i + 1;
    }
  
    // Return final ans
    return ans;
}
  
// Driver Code
int32_t main()
{
    int arr[] = { 1, 2, 3, 4, 5, 1, 2, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << largest_subarray(arr, n);
}

Java

// Java program to implement
// the above approach
import java.util.*;
class GFG{
  
// Function to find largest
// subarray with no duplicates
static int largest_subarray(int a[], int n)
{
    // Stores index of array elements
    HashMap<Integer,
            Integer> index = new HashMap<Integer,
                                         Integer>();
    int ans = 0;
    for(int i = 0, j = 0; i < n; i++)
    {
  
        // Update j based on previous
        // occurrence of a[i]
        j = Math.max(index.containsKey(a[i]) ? 
                             index.get(a[i]) : 0, j);
  
        // Update ans to store maximum
        // length of subarray
        ans = Math.max(ans, i - j + 1);
  
        // Store the index of current
        // occurrence of a[i]
        index.put(a[i], i + 1);
    }
  
    // Return final ans
    return ans;
}
  
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, 4, 5, 1, 2, 3 };
    int n = arr.length;
    System.out.print(largest_subarray(arr, n));
}
}
  
// This code is contributed by Rajput-Ji

Python3

# Python3 program to implement
# the above approach
from collections import defaultdict
  
# Function to find largest
# subarray with no duplicates
def largest_subarray(a, n):
  
    # Stores index of array elements
    index = defaultdict(lambda : 0)
      
    ans = 0
    j = 0
  
    for i in range(n):
  
        # Update j based on previous
        # occurrence of a[i]
        j = max(index[a[i]], j)
  
        # Update ans to store maximum
        # length of subarray
        ans = max(ans, i - j + 1)
  
        # Store the index of current
        # occurrence of a[i]
        index[a[i]] = i + 1
  
        i += 1
  
    # Return final ans 
    return ans
  
# Driver Code
arr = [ 1, 2, 3, 4, 5, 1, 2, 3 ]
n = len(arr)
  
# Function call
print(largest_subarray(arr, n))
  
# This code is contributed by Shivam Singh

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
  
class GFG{
  
// Function to find largest
// subarray with no duplicates
static int largest_subarray(int []a, int n)
{
      
    // Stores index of array elements
    Dictionary<int,
               int> index = new Dictionary<int,
                                           int>();
    int ans = 0;
    for(int i = 0, j = 0; i < n; i++)
    {
  
        // Update j based on previous
        // occurrence of a[i]
        j = Math.Max(index.ContainsKey(a[i]) ? 
                                 index[a[i]] : 0, j);
  
        // Update ans to store maximum
        // length of subarray
        ans = Math.Max(ans, i - j + 1);
  
        // Store the index of current
        // occurrence of a[i]
        if(index.ContainsKey(a[i]))
            index[a[i]] = i + 1;
        else
            index.Add(a[i], i + 1);
    }
  
    // Return readonly ans
    return ans;
}
  
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 3, 4, 5, 1, 2, 3 };
    int n = arr.Length;
      
    Console.Write(largest_subarray(arr, n));
}
}
  
// This code is contributed by Amit Katiyar

Javascript

<script>
  
// Javascript program to implement
// the above approach
  
// Function to find largest
// subarray with no duplicates
function largest_subarray(a, n)
{
    // Stores index of array elements
    let index = new Map();
    let ans = 0;
    for(let i = 0, j = 0; i < n; i++)
    {
   
        // Update j based on previous
        // occurrence of a[i]
        j = Math.max(index.has(a[i]) ?
                             index.get(a[i]) : 0, j);
   
        // Update ans to store maximum
        // length of subarray
        ans = Math.max(ans, i - j + 1);
   
        // Store the index of current
        // occurrence of a[i]
        index.set(a[i], i + 1);
    }
   
    // Return final ans
    return ans;
}
  
// Driver code
  
    let arr = [ 1, 2, 3, 4, 5, 1, 2, 3 ];
    let n = arr.length;
    document.write(largest_subarray(arr, n));
  
</script>
Producción: 

5

 

Complejidad de tiempo: O(N) en el mejor de los casos y O(n^2) en el peor de los casos.

NOTA: Podemos hacer que la complejidad del tiempo sea igual a O(n * logn) usando estructuras de árboles binarios equilibrados (`std::map` en C++ y `TreeMap` en Java) en lugar de estructuras Hash.
Espacio Auxiliar: O(N)

Tema relacionado: Subarrays, subsecuencias y subconjuntos en array

Publicación traducida automáticamente

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