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: 5
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: 8
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:
- 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
- Recorra la array y siga actualizando j en función de la aparición anterior de a[i] almacenada en HashMap.
- Después de actualizar j , actualice ans en consecuencia para almacenar la longitud máxima del subarreglo deseado.
- 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>
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