Dado un arreglo arr de enteros positivos, la tarea es encontrar el subarreglo de longitud más pequeña de longitud mayor que 1 que tenga un elemento que aparezca más veces que cualquier otro elemento.
Ejemplos:
Entrada: arr[] = {2, 3, 2, 4, 5}
Salida: 2 3 2
Explicación: El subarreglo {2, 3, 2} tiene un elemento 2 que aparece más veces que cualquier otro elemento del subarreglo.Entrada: arr[] = {2, 3, 4, 5, 2, 6, 7, 6}
Salida: 6 7 6
Explicación: Los subarreglos {2, 3, 4, 5, 2} y {6, 7, 6 } contienen un elemento que ocurre más veces que cualquier otro elemento en ellos. Pero el subarreglo {6, 7, 6} tiene una longitud mínima.
Enfoque ingenuo: un enfoque ingenuo para resolver el problema puede ser encontrar todos los subarreglos que tienen un elemento que cumple con la condición dada y luego encontrar el mínimo de todos esos subarreglos.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: el problema se puede reducir para descubrir que si hay algún elemento que ocurre dos veces en un subarreglo, entonces puede ser una respuesta potencial. Porque la longitud mínima de tal subarreglo puede ser la distancia mínima entre dos mismos elementos
La idea es usar una array adicional que mantenga la última aparición de los elementos en la array dada. Luego encuentre la distancia entre la última ocurrencia de un elemento y la posición actual y encuentre el mínimo de todas esas longitudes.
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 find subarray
void FindSubarray(int arr[], int n)
{
// If the array has only one element,
// then there is no answer.
if (n == 1) {
cout << "No such subarray!"
<< endl;
}
// Array to store the last occurrences
// of the elements of the array.
int vis[n + 1];
memset(vis, -1, sizeof(vis));
vis[arr[0]] = 0;
// To maintain the length
int len = INT_MAX, flag = 0;
// Variables to store
// start and end indices
int start, end;
for (int i = 1; i < n; i++) {
int t = arr[i];
// Check if element is occurring
// for the second time in the array
if (vis[t] != -1) {
// Find distance between last
// and current index
// of the element.
int distance = i - vis[t] + 1;
// If the current distance
// is less then len
// update len and
// set 'start' and 'end'
if (distance < len) {
len = distance;
start = vis[t];
end = i;
}
flag = 1;
}
// Set the last occurrence
// of current element to be 'i'.
vis[t] = i;
}
// If flag is equal to 0,
// it means there is no answer.
if (flag == 0)
cout << "No such subarray!"
<< endl;
else {
for (int i = start; i <= end; i++)
cout << arr[i] << " ";
}
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 2, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
FindSubarray(arr, n);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find subarray
public static void FindSubarray(int[] arr,
int n)
{
// If the array has only one element,
// then there is no answer.
if (n == 1)
{
System.out.println("No such subarray!");
}
// Array to store the last occurrences
// of the elements of the array.
int[] vis = new int[n + 1];
Arrays.fill(vis, -1);
vis[arr[0]] = 0;
// To maintain the length
int len = Integer.MAX_VALUE, flag = 0;
// Variables to store
// start and end indices
int start = 0, end = 0;
for(int i = 1; i < n; i++)
{
int t = arr[i];
// Check if element is occurring
// for the second time in the array
if (vis[t] != -1)
{
// Find distance between last
// and current index
// of the element.
int distance = i - vis[t] + 1;
// If the current distance
// is less then len
// update len and
// set 'start' and 'end'
if (distance < len)
{
len = distance;
start = vis[t];
end = i;
}
flag = 1;
}
// Set the last occurrence
// of current element to be 'i'.
vis[t] = i;
}
// If flag is equal to 0,
// it means there is no answer.
if (flag == 0)
System.out.println("No such subarray!");
else
{
for(int i = start; i <= end; i++)
System.out.print(arr[i] + " ");
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 3, 2, 4, 5 };
int n = arr.length;
FindSubarray(arr, n);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program for the above approach
import sys
# Function to find subarray
def FindSubarray(arr, n):
# If the array has only one element,
# then there is no answer.
if (n == 1):
print("No such subarray!")
# Array to store the last occurrences
# of the elements of the array.
vis = [-1] * (n + 1)
vis[arr[0]] = 0
# To maintain the length
length = sys.maxsize
flag = 0
for i in range(1, n):
t = arr[i]
# Check if element is occurring
# for the second time in the array
if (vis[t] != -1):
# Find distance between last
# and current index
# of the element.
distance = i - vis[t] + 1
# If the current distance
# is less then len
# update len and
# set 'start' and 'end'
if (distance < length):
length = distance
start = vis[t]
end = i
flag = 1
# Set the last occurrence
# of current element to be 'i'.
vis[t] = i
# If flag is equal to 0,
# it means there is no answer.
if (flag == 0):
print("No such subarray!")
else:
for i in range(start, end + 1):
print(arr[i], end = " ")
# Driver Code
if __name__ == "__main__":
arr = [ 2, 3, 2, 4, 5 ]
n = len(arr)
FindSubarray(arr, n)
# This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
class GFG{
// Function to find subarray
public static void FindSubarray(int[] arr,
int n)
{
// If the array has only one element,
// then there is no answer.
if (n == 1)
{
Console.WriteLine("No such subarray!");
}
// Array to store the last occurrences
// of the elements of the array.
int[] vis = new int[n + 1];
for(int i = 0; i < n + 1; i++)
vis[i] = -1;
vis[arr[0]] = 0;
// To maintain the length
int len = int.MaxValue, flag = 0;
// Variables to store
// start and end indices
int start = 0, end = 0;
for(int i = 1; i < n; i++)
{
int t = arr[i];
// Check if element is occurring
// for the second time in the array
if (vis[t] != -1)
{
// Find distance between last
// and current index
// of the element.
int distance = i - vis[t] + 1;
// If the current distance
// is less then len
// update len and
// set 'start' and 'end'
if (distance < len)
{
len = distance;
start = vis[t];
end = i;
}
flag = 1;
}
// Set the last occurrence
// of current element to be 'i'.
vis[t] = i;
}
// If flag is equal to 0,
// it means there is no answer.
if (flag == 0)
Console.WriteLine("No such subarray!");
else
{
for(int i = start; i <= end; i++)
Console.Write(arr[i] + " ");
}
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 2, 3, 2, 4, 5 };
int n = arr.Length;
FindSubarray(arr, n);
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript program for the above approach
// Function to find subarray
function FindSubarray(arr, n)
{
// If the array has only one element,
// then there is no answer.
if (n == 1)
{
document.write("No such subarray!");
}
// Array to store the last occurrences
// of the elements of the array.
let vis = new Array(n + 1);
for(let i = 0; i < (n + 1); i++)
vis[i] = -1;
vis[arr[0]] = 0;
// To maintain the length
let len = Number.MAX_VALUE, flag = 0;
// Variables to store
// start and end indices
let start = 0, end = 0;
for(let i = 1; i < n; i++)
{
let t = arr[i];
// Check if element is occurring
// for the second time in the array
if (vis[t] != -1)
{
// Find distance between last
// and current index
// of the element.
let distance = i - vis[t] + 1;
// If the current distance
// is less then len
// update len and
// set 'start' and 'end'
if (distance < len)
{
len = distance;
start = vis[t];
end = i;
}
flag = 1;
}
// Set the last occurrence
// of current element to be 'i'.
vis[t] = i;
}
// If flag is equal to 0,
// it means there is no answer.
if (flag == 0)
document.write("No such subarray!");
else
{
for(let i = start; i <= end; i++)
document.write(arr[i] + " ");
}
}
// Driver code
let arr = [ 2, 3, 2, 4, 5 ];
let n = arr.length;
FindSubarray(arr, n);
// This code is contributed by avanitrachhadiya2155
</script>
2 3 2
Complejidad de tiempo: O(N) , donde n es la longitud de la array.
Espacio Auxiliar: O(N) .
Publicación traducida automáticamente
Artículo escrito por vashisthamadhur2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA