Dada una array de N elementos, la tarea es encontrar la longitud del subarreglo más pequeño de la array dada que contiene al menos un elemento duplicado. Un subarreglo se forma a partir de elementos consecutivos de un arreglo. Si no existe tal array, imprima «-1».
Ejemplos:
Input: arr = {1, 2, 3, 1, 5, 4, 5}
Output: 3
Explanation:
Input: arr = {4, 7, 11, 3, 1, 2, 4}
Output: 7
Explanation:
Enfoque ingenuo:
- El truco consiste en encontrar todos los pares de dos elementos con el mismo valor. Dado que estos dos elementos tienen el mismo valor, el subarreglo que los encierra tendría al menos un único duplicado y sería uno de los candidatos para la respuesta.
- Una solución simple es usar dos bucles anidados para encontrar cada par de elementos. Si los dos elementos son iguales, actualice la longitud máxima obtenida hasta el momento.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find
// the smallest subarray having
// atleast one duplicate
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// SubArray Length
int subArrayLength(int arr[], int n)
{
int minLen = INT_MAX;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
// If the two elements are equal,
// then the subarray arr[i..j]
// will definitely have a duplicate
if (arr[i] == arr[j]) {
// Update the minimum length
// obtained so far
minLen = min(minLen, i - j + 1);
}
}
}
if (minLen == INT_MAX) {
return -1;
}
return minLen;
}
// Driver Code
int main()
{
int n = 7;
int arr[] = { 1, 2, 3, 1, 5, 4, 5 };
int ans = subArrayLength(arr, n);
cout << ans << '\n';
return 0;
}
Java
// Java program to find
// the smallest subarray having
// atleast one duplicate
class GFG
{
final static int INT_MAX = Integer.MAX_VALUE;
// Function to calculate
// SubArray Length
static int subArrayLength(int arr[], int n)
{
int minLen = INT_MAX;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
// If the two elements are equal,
// then the subarray arr[i..j]
// will definitely have a duplicate
if (arr[i] == arr[j])
{
// Update the minimum length
// obtained so far
minLen = Math.min(minLen, i - j + 1);
}
}
}
if (minLen == INT_MAX)
{
return -1;
}
return minLen;
}
// Driver Code
public static void main(String[] args)
{
int n = 7;
int arr[] = { 1, 2, 3, 1, 5, 4, 5 };
int ans = subArrayLength(arr, n);
System.out.println(ans);
}
}
// This code is contributed by AnkitRai01
Python
# Python program for above approach
n = 7
arr = [1, 2, 3, 1, 5, 4, 5]
minLen = n + 1
for i in range(1, n):
for j in range(0, i):
if arr[i]== arr[j]:
minLen = min(minLen, i-j + 1)
if minLen == n + 1:
print("-1")
else:
print(minLen)
C#
// C# program to find
// the smallest subarray having
// atleast one duplicate
using System;
class GFG
{
static int INT_MAX = int.MaxValue;
// Function to calculate
// SubArray Length
static int subArrayLength(int []arr, int n)
{
int minLen = INT_MAX;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
// If the two elements are equal,
// then the subarray arr[i..j]
// will definitely have a duplicate
if (arr[i] == arr[j])
{
// Update the minimum length
// obtained so far
minLen = Math.Min(minLen, i - j + 1);
}
}
}
if (minLen == INT_MAX)
{
return -1;
}
return minLen;
}
// Driver Code
public static void Main()
{
int n = 7;
int []arr = { 1, 2, 3, 1, 5, 4, 5 };
int ans = subArrayLength(arr, n);
Console.WriteLine(ans);
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// javascript program to find
// the smallest subarray having
// atleast one duplicate
var INT_MAX = Number.MAX_VALUE;
// Function to calculate
// SubArray Length
function subArrayLength( arr , n) {
var minLen = INT_MAX;
for (var i = 1; i < n; i++) {
for (var j = 0; j < i; j++) {
// If the two elements are equal,
// then the subarray arr[i..j]
// will definitely have a duplicate
if (arr[i] == arr[j]) {
// Update the minimum length
// obtained so far
minLen = Math.min(minLen, i - j + 1);
}
}
}
if (minLen == INT_MAX) {
return -1;
}
return minLen;
}
// Driver Code
var n = 7;
var arr = [ 1, 2, 3, 1, 5, 4, 5 ];
var ans = subArrayLength(arr, n);
document.write(ans);
// This code contributed by Princi Singh
</script>
Producción:
3
Complejidad de Tiempo: Enfoque Eficiente O(N 2 )
:
Este problema puede ser resuelto en tiempo O(N) y espacio Auxiliar O(N) usando la idea de la técnica hash . La idea es iterar a través de cada elemento de la array de forma lineal y, para cada elemento, encontrar su última aparición usando un hashmap y luego actualizar el valor de la longitud mínima usando la diferencia de la última aparición y el índice actual. Además, actualice el valor de la última aparición del elemento por el valor del índice actual.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find
// the smallest subarray having
// atleast one duplicate
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// SubArray Length
int subArrayLength(int arr[], int n)
{
int minLen = INT_MAX;
// Last stores the index of the last
// occurrence of the corresponding value
unordered_map<int, int> last;
for (int i = 0; i < n; i++) {
// If the element has already occurred
if (last[arr[i]] != 0) {
minLen = min(minLen, i - last[arr[i]] + 2);
}
last[arr[i]] = i + 1;
}
if (minLen == INT_MAX) {
return -1;
}
return minLen;
}
// Driver Code
int main()
{
int n = 7;
int arr[] = { 1, 2, 3, 1, 5, 4, 5 };
int ans = subArrayLength(arr, n);
cout << ans << '\n';
return 0;
}
Java
// Java program to find
// the smallest subarray having
// atleast one duplicate
import java.util.*;
class GFG
{
// Function to calculate
// SubArray Length
static int subArrayLength(int arr[], int n)
{
int minLen = Integer.MAX_VALUE;
// Last stores the index of the last
// occurrence of the corresponding value
HashMap<Integer, Integer> last = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++)
{
// If the element has already occurred
if (last.containsKey(arr[i]) && last.get(arr[i]) != 0)
{
minLen = Math.min(minLen, i - last.get(arr[i]) + 2);
}
last.put(arr[i], i + 1);
}
if (minLen == Integer.MAX_VALUE)
{
return -1;
}
return minLen;
}
// Driver Code
public static void main(String[] args)
{
int n = 7;
int arr[] = { 1, 2, 3, 1, 5, 4, 5 };
int ans = subArrayLength(arr, n);
System.out.print(ans);
}
}
// This code is contributed by 29AjayKumar
Python
# Python program for above approach
n = 7
arr = [1, 2, 3, 1, 5, 4, 5]
last = dict()
minLen = n + 1
for i in range(0, n):
if arr[i] in last:
minLen = min(minLen, i-last[arr[i]]+2)
last[arr[i]]= i + 1
if minLen == n + 1:
print("-1")
else:
print(minLen)
C#
// C# program to find
// the smallest subarray having
// atleast one duplicate
using System;
using System.Collections.Generic;
class GFG
{
// Function to calculate
// SubArray Length
static int subArrayLength(int []arr, int n)
{
int minLen = int.MaxValue;
// Last stores the index of the last
// occurrence of the corresponding value
Dictionary<int, int> last = new Dictionary<int, int>();
for (int i = 0; i < n; i++)
{
// If the element has already occurred
if (last.ContainsKey(arr[i]) && last[arr[i]] != 0)
{
minLen = Math.Min(minLen, i - last[arr[i]] + 2);
}
if(last.ContainsKey(arr[i]))
last[arr[i]] = i + 1;
else
last.Add(arr[i], i + 1);
}
if (minLen == int.MaxValue)
{
return -1;
}
return minLen;
}
// Driver Code
public static void Main(String[] args)
{
int n = 7;
int []arr = { 1, 2, 3, 1, 5, 4, 5 };
int ans = subArrayLength(arr, n);
Console.Write(ans);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to find
// the smallest subarray having
// atleast one duplicate
// Function to calculate
// SubArray Length
function subArrayLength(arr, n)
{
let minLen = Number.MAX_VALUE;
// Last stores the index of the last
// occurrence of the corresponding value
let last = new Map();
for (let i = 0; i < n; i++)
{
// If the element has already occurred
if (last.has(arr[i]) && last.get(arr[i]) != 0)
{
minLen =
Math.min(minLen, i - last.get(arr[i]) + 2);
}
last.set(arr[i], i + 1);
}
if (minLen == Number.MAX_VALUE)
{
return -1;
}
return minLen;
}
// Driver code
let n = 7;
let arr = [ 1, 2, 3, 1, 5, 4, 5 ];
let ans = subArrayLength(arr, n);
document.write(ans);
</script>
Producción:
3
Complejidad de tiempo: O(N), donde N es el tamaño de la array
Publicación traducida automáticamente
Artículo escrito por PrakharBansal1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA