Nos dan una array que consta de n enteros y un entero k. Necesitamos encontrar el rango mínimo en el arreglo [l, r] (tanto l como r son inclusivos) tal que haya exactamente k números diferentes. Si tal subarreglo no existe, imprima «K no válido».
Ejemplos:
Input : arr[] = { 1, 1, 2, 2, 3, 3, 4, 5}
k = 3
Output : 5 7
Input : arr[] = { 1, 2, 2, 3}
k = 2
Output : 0 1
Input : arr[] = {1, 1, 2, 1, 2}
k = 3
Output : Invalid k
Enfoque 1: (Método de fuerza bruta)
El enfoque más simple en este problema es intentar generar todos los subarreglos y verificar para qué subarreglo el tamaño es k. Pero hay algunos puntos que debemos cuidar.
Pasos:
- Elija cada uno de los elementos de la array dada como el elemento inicial [i-ésimo elemento] de nuestra subarreglo requerido.
- En cada iteración, inicialice un conjunto vacío para almacenar los distintos elementos del subarreglo
- Elija cada elemento restante [i, i+1,..n – 1] de la array como el último elemento [j-ésimo elemento].
- Añade el elemento actual al conjunto.
- Si el tamaño del conjunto es igual a k , actualice los resultados y rompa con el ciclo interno (ya se encontraron k elementos distintos que aumentan el tamaño del subarreglo tiene 2 posibilidades, obtendrá más elementos distintos o aumentará el tamaño del subarreglo con elementos repetidos que no son para considerarse en los resultados requeridos).
- Si (j == n) o j = tamaño de la array, es decir, no hemos encontrado ningún subarreglo deseado a partir del i-ésimo índice y en el futuro tendremos menos elementos para considerar.
(Por ejemplo: considere que el conjunto dado es 4 5 5 4 5 y k = 3 , cuando comience desde el índice 0 no encontraremos ningún subarreglo de tamaño k y j llegará al final, lo que significa que no obtendremos ningún elemento que pueda hacer ak = 3 subarreglo de tamaño requerido).
Entonces, rompe con el bucle exterior. - Imprima la salida si la encuentra; de lo contrario, imprima «K no válida» .
Implementación:
C++
// C++ program to find minimum range that
// contains exactly k distinct numbers.
#include <bits/stdc++.h>
using namespace std;
// Prints the minimum range that contains exactly
// k distinct numbers.
void minRange(int arr[], int n, int k)
{
// Starting and ending index of resultant subarray
int start = 0, end = n;
// Selecting each element as the start index for
// subarray
for (int i = 0; i < n; i++) {
// Initialize a set to store all distinct elements
unordered_set<int> set;
// Selecting the end index for subarray
int j;
for (j = i; j < n; j++) {
set.insert(arr[j]);
/*
If set contains exactly k elements,
then check subarray[i, j] is smaller in size
than the current resultant subarray
*/
if (set.size() == k) {
if (j - i < end - start) {
start = i;
end = j;
}
// There are already k distinct elements
// now, no need to consider further elements
break;
}
}
// If there are no k distinct elements
// left in the array starting from index i we will
// break
if (j == n) {
break;
}
}
// If no window found then print -1
if (start == 0 && end == n)
cout << "Invalid k";
else
cout << start << " " << end;
}
// Driver code for above function.
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
minRange(arr, n, k);
return 0;
}
// This code is contributed by Rajdeep
Java
// Java program to find minimum
// range that contains exactly
// k distinct numbers.
import java.util.*;
import java.util.ArrayList;
import java.util.HashSet;
class GFG {
// Prints the minimum range
// that contains exactly k
// distinct numbers.
static void minRange(int arr[], int n, int k)
{
// start -> start index of resultant subarray
// end -> end index of resultant subarray
int start = 0;
int end = n;
// Selecting each element as the start index for
// subarray
for (int i = 0; i < n; i++) {
// Initialize a set to store all distinct
// elements
HashSet<Integer> set = new HashSet<Integer>();
// Selecting the end index for subarray
int j;
for (j = i; j < n; j++) {
set.add(arr[j]);
/*
If set contains exactly k
elements,then check subarray[i, j]
is smaller in size than the current
resultant subarray
*/
if (set.size() == k)
{
if (j - i < end - start) {
start = i;
end = j;
}
// There are already 'k' distinct
// elements now, no need to consider
// further elements
break;
}
}
// If there are no k distinct elements left
// in the array starting from index i we will break
if (j == n)
break;
}
// If no window found then print -1
if (start == 0 && end == n)
System.out.println("Invalid k");
else
System.out.println(start + " " + end);
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 2, 3, 4, 5 };
int n = arr.length;
int k = 3;
minRange(arr, n, k);
}
}
// This code is contributed by Rajdeep
Python 3
# Python 3 program to find minimum range
# that contains exactly k distinct numbers.
# Prints the minimum range that contains
# exactly k distinct numbers.
def minRange(arr, n, k):
l = 0
r = n
# Consider every element as
# starting point.
for i in range(n):
# Find the smallest window starting
# with arr[i] and containing exactly
# k distinct elements.
s = []
for j in range(i, n) :
s.append(arr[j])
if (len(s) == k):
if ((j - i) < (r - l)) :
r = j
l = i
break
# There are less than k distinct
# elements now, so no need to continue.
if (j == n):
break
# If there was no window with k distinct
# elements (k is greater than total
# distinct elements)
if (l == 0 and r == n):
print("Invalid k")
else:
print(l, r)
# Driver code
if __name__ == "__main__":
arr = [ 1, 2, 3, 4, 5 ]
n = len(arr)
k = 3
minRange(arr, n, k)
# This code is contributed
# by ChitraNayal
C#
// C# program to find minimum
// range that contains exactly
// k distinct numbers.
using System;
using System.Collections.Generic;
public class GFG
{
// Prints the minimum range
// that contains exactly k
// distinct numbers.
public static void minRange(int[] arr, int n, int k)
{
int l = 0, r = n;
// Consider every element
// as starting point.
for (int i = 0; i < n; i++)
{
// Find the smallest window
// starting with arr[i] and
// containing exactly k
// distinct elements.
ISet<int> s = new HashSet<int>();
int j;
for (j = i; j < n; j++)
{
s.Add(arr[j]);
if (s.Count == k)
{
if ((j - i) < (r - l))
{
r = j;
l = i;
}
break;
}
}
// There are less than k
// distinct elements now,
// so no need to continue.
if (j == n)
{
break;
}
}
// If there was no window
// with k distinct elements
// (k is greater than total
// distinct elements)
if (l == 0 && r == n)
{
Console.WriteLine("Invalid k");
}
else
{
Console.WriteLine(l + " " + r);
}
}
// Driver code
public static void Main(string[] args)
{
int[] arr = new int[] {1, 2, 3, 4, 5};
int n = arr.Length;
int k = 3;
minRange(arr, n, k);
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// Javascript program to find minimum
// range that contains exactly
// k distinct numbers.
// Prints the minimum range
// that contains exactly k
// distinct numbers.
function minRange(arr,n,k)
{
let l = 0, r = n;
// Consider every element
// as starting point.
for (let i = 0; i < n; i++)
{
// Find the smallest window
// starting with arr[i] and
// containing exactly k
// distinct elements.
let s = new Set();
let j;
for (j = i; j < n; j++)
{
s.add(arr[j]);
if (s.size == k)
{
if ((j - i) < (r - l))
{
r = j;
l = i;
}
break;
}
}
// There are less than k
// distinct elements now,
// so no need to continue.
if (j == n)
break;
}
// If there was no window
// with k distinct elements
// (k is greater than total
// distinct elements)
if (l == 0 && r == n)
document.write("Invalid k");
else
document.write(l + " " + r);
}
// Driver code
let arr=[1, 2, 3, 4, 5];
let n = arr.length;
let k = 3;
minRange(arr, n, k);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
0 2
Complejidad de tiempo: O (N ^ 2) , donde N es el número de elementos en la array. Cada vez que se seleccionan los puntos finales del subarreglo usando dos bucles anidados (uno dentro de otro), la complejidad del tiempo es O (N ^ 2).
Complejidad espacial: O (N), en el peor de los casos, podemos tener todos los elementos ‘N’ en nuestro conjunto.
Enfoque 2: (Enfoque de ventana deslizante)
La optimización es deshacerse del trabajo repetido al hacer todos los subarreglos, todos los subarreglos no ayudarán a encontrar el resultante. El enfoque es –
Pasos :
- Inicialice un mapa para almacenar las frecuencias de cada elemento.
- Tomando dos variables como se tomaron antes: inicio y final del subarreglo requerido.
- Y aquí estamos usando i y j como el índice inicial y final de la ventana respectivamente, inicializando como i = 0 y j = 0 .
- Recorrerá la array mientras el puntero final de nuestra ventana alcance el final de la array dada. es decir , mientras ( j < n)
- Agregue el elemento actual al mapa map[ arr[j] ]++ y haga que j apunte al siguiente índice
- Considere la ventana [i, j-1] (el motivo de ‘j-1’ es que incrementamos el valor de ‘j’ justo después de la inserción en el último paso) verifique si su tamaño es igual a k
- Si el tamaño de la ventana es menor que k , continúe
- Pero si el tamaño de la ventana == k , entonces verifique su longitud si es el subarreglo resultante o no.
- Después de eso, necesitamos mover nuestra ventana, pero para mover nuestra ventana, debemos verificar el elemento inicial de nuestra ventana actual (es decir , i-th ). Si el i-ésimo elemento tiene una frecuencia de 1, bórrelo del mapa y disminuya su frecuencia en 1. Y aumente el valor de i. Haz que i apunte al siguiente elemento.
(Para comprender el motivo del borrado y la disminución de la frecuencia, tome un ejemplo: 4 2 2 3 4 4 3 y k = 3 cuando estamos tratando con la ventana 2 2 3 4 entonces ‘i’ habría apuntado al inicio de la ventana ( primero 2 ) y ‘j’ habría apuntado a la última ventana (en 4 ). Ahora, mientras avanza (una posición), si la ventana borra totalmente 2 del mapa, (y hace que la ventana sea 2 3 4 4 ), entonces map contendría la información de que 2 no está en el mapa pero está malpor lo que disminuiremos la cuenta de 2. De igual forma, en caso de tener frecuencia == 1, ya punto de salir de la ventana, el mapa no debe contener la frecuencia del elemento que no está en la ventana. )
Implementación:
C++
// C++ program to find minimum range that
// contains exactly k distinct numbers.
#include <bits/stdc++.h>
using namespace std;
// prints the minimum range that contains exactly
// k distinct numbers.
void minRange(int arr[], int n, int k)
{
/*
start = starting index of resultant subarray
end = ending index of resultant subarray
*/
int start = 0, end = n;
unordered_map<int, int> map;
/*
i = starting index of the window (on left side)
j = ending index of the window (on right side)
*/
int i = 0, j = 0;
while (j < n) {
// Add the current element to the map
map[arr[j]]++;
j++;
// Nothing to do when having less element
if (map.size() < k)
continue;
/*
If map contains exactly k elements,
consider subarray[i, j - 1] keep removing
left most elements
*/
while (map.size() == k) {
// as considering the (j-1)th and i-th index
int windowLen = (j - 1) - i + 1;
int subArrayLen = end - start + 1;
if (subArrayLen > windowLen) {
start = i;
end = j - 1;
}
// Remove elements from left
// If freq == 1 then totally erase
if (map[arr[i]] == 1)
map.erase(arr[i]);
// decrease freq by 1
else
map[arr[i]]--;
// move the starting index of window
i++;
}
}
if (start == 0 && end == n)
cout << "Invalid k" << endl;
else
cout << start << " " << end << endl;
}
// Driver code for above function.
int main()
{
int arr[] = { 1, 1, 2, 2, 3, 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
minRange(arr, n, k);
return 0;
}
// This code is contributed by Rajdeep
Java
// Java program to find minimum range that
// contains exactly k distinct numbers.
import java.util.*;
class GFG {
// Prints the minimum range that contains exactly
// k distinct numbers.
static void minRange(int arr[], int n, int k)
{
/*
start = starting index of resultant subarray
end = ending index of resultant subarray
*/
int start = 0, end = n;
HashMap<Integer, Integer> map = new HashMap<>();
/*
i = starting index of the window (on left side)
j = ending index of the window (on right side)
*/
int i = 0, j = 0;
while (j < n) {
// Add the current element to the map
map.put(arr[j], map.getOrDefault(arr[j], 0) + 1);
j++;
// Nothing to do when having less element
if (map.size() < k)
continue;
/*
If map contains exactly k elements,
consider subarray[i, j - 1] keep removing
left most elements
*/
while (map.size() == k)
{
// as considering the (j-1)th and i-th index
int windowLen = (j - 1) - i + 1;
int subArrayLen = end - start + 1;
if (windowLen < subArrayLen) {
start = i;
end = j - 1;
}
// Remove elements from left
// If freq == 1 then totally erase
if (map.get(arr[i]) == 1)
map.remove(arr[i]);
// decrease freq by 1
else
map.put(arr[i], map.get(arr[i]) - 1);
// move the starting index of window
i++;
}
}
if (start == 0 && end == n)
System.out.println("Invalid k");
else
System.out.println(start + " " + end);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 1, 2, 2, 3, 3, 4, 5 };
int n = arr.length;
int k = 3;
minRange(arr, n, k);
}
}
// This code is contributed by Rajdeep
Python3
# Python3 program to find the minimum range
# that contains exactly k distinct numbers.
from collections import defaultdict
# Prints the minimum range that contains
# exactly k distinct numbers.
def minRange(arr, n, k):
# Initially left and right side is -1
# and -1, number of distinct elements
# are zero and range is n.
l, r = 0, n
i = 0
j = -1 # Initialize right side
hm = defaultdict(lambda:0)
while i < n:
while j < n:
# increment right side.
j += 1
# if number of distinct elements less than k.
if len(hm) < k and j < n:
hm[arr[j]] += 1
# if distinct elements are equal to k
# and length is less than previous length.
if len(hm) == k and ((r - l) >= (j - i)):
l, r = i, j
break
# if number of distinct elements less
# than k, then break.
if len(hm) < k:
break
# if distinct elements equals to k then
# try to increment left side.
while len(hm) == k:
if hm[arr[i]] == 1:
del(hm[arr[i]])
else:
hm[arr[i]] -= 1
# increment left side.
i += 1
# it is same as explained in above loop.
if len(hm) == k and (r - l) >= (j - i):
l, r = i, j
if hm[arr[i]] == 1:
del(hm[arr[i]])
else:
hm[arr[i]] -= 1
i += 1
if l == 0 and r == n:
print("Invalid k")
else:
print(l, r)
# Driver code for above function.
if __name__ == "__main__":
arr = [1, 1, 2, 2, 3, 3, 4, 5]
n = len(arr)
k = 3
minRange(arr, n, k)
# This code is contributed by Rituraj Jain
C#
// C# program to find minimum
// range that contains exactly
// k distinct numbers.
using System;
using System.Collections.Generic;
class GFG{
// Prints the minimum
// range that contains exactly
// k distinct numbers.
static void minRange(int []arr,
int n, int k)
{
// Initially left and
// right side is -1 and -1,
// number of distinct
// elements are zero and
// range is n.
int l = 0, r = n;
// Initialize right side
int j = -1;
Dictionary<int,
int> hm = new Dictionary<int,
int>();
for(int i = 0; i < n; i++)
{
while (j < n)
{
// Increment right side.
j++;
// If number of distinct elements less
// than k.
if (j < n && hm.Count < k)
if(hm.ContainsKey(arr[j]))
hm[arr[j]] = hm[arr[j]] + 1;
else
hm.Add(arr[j], 1);
// If distinct elements are equal to k
// and length is less than previous length.
if (hm.Count == k &&
((r - l) >= (j - i)))
{
l = i;
r = j;
break;
}
}
// If number of distinct elements less
// than k, then break.
if (hm.Count < k)
break;
// If distinct elements equals to k then
// try to increment left side.
while (hm.Count == k)
{
if (hm.ContainsKey(arr[i]) &&
hm[arr[i]] == 1)
hm.Remove(arr[i]);
else
{
if(hm.ContainsKey(arr[i]))
hm[arr[i]] = hm[arr[i]] - 1;
}
// Increment left side.
i++;
// It is same as explained in above loop.
if (hm.Count == k &&
(r - l) >= (j - i))
{
l = i;
r = j;
}
}
if (hm.ContainsKey(arr[i]) &&
hm[arr[i]] == 1)
hm.Remove(arr[i]);
else
if(hm.ContainsKey(arr[i]))
hm[arr[i]] = hm[arr[i]] - 1;
}
if (l == 0 && r == n)
Console.WriteLine("Invalid k");
else
Console.WriteLine(l + " " + r);
}
// Driver code
public static void Main(String[] args)
{
int []arr = {1, 1, 2, 2,
3, 3, 4, 5};
int n = arr.Length;
int k = 3;
minRange(arr, n, k);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to find minimum
// range that contains exactly
// k distinct numbers
// Prints the minimum
// range that contains exactly
// k distinct numbers.
function minRange(arr,n,k)
{
// Initially left and right side is -1 and -1,
// number of distinct elements are zero and
// range is n.
let l = 0, r = n;
// Initialize right side
let j = -1;
let hm = new Map();
for(let i = 0; i < n; i++)
{
while (j < n)
{
// Increment right side.
j++;
// If number of distinct elements less
// than k.
if (j < n && hm.size < k)
{
if(hm.has(arr[j]))
hm.set(arr[j],
hm.get(arr[j]) + 1);
else
hm.set(arr[j],1);
}
// If distinct elements are equal to k
// and length is less than previous length.
if (hm.size == k &&
((r - l) >= (j - i)))
{
l = i;
r = j;
break;
}
}
// If number of distinct elements less
// than k, then break.
if (hm.size < k)
break;
// If distinct elements equals to k then
// try to increment left side.
while (hm.size == k)
{
if (hm.has(arr[i]) && hm.get(arr[i]) == 1)
hm.delete(arr[i]);
else
if(hm.has(arr[i]))
hm.set(arr[i],hm.get(arr[i]) - 1);
// Increment left side.
i++;
// It is same as explained in above loop.
if (hm.size == k &&
(r - l) >= (j - i))
{
l = i;
r = j;
}
}
if (hm.has(arr[i]) && hm.get(arr[i]) == 1)
hm.delete(arr[i]);
else
if(hm.has(arr[i]))
hm.set(arr[i],hm.get(arr[i]) - 1);
}
if (l == 0 && r == n)
document.write("Invalid k");
else
document.write(l + " " + r);
}
// Driver code
let arr=[1, 1, 2, 2, 3, 3, 4, 5];
let n = arr.length;
let k = 3;
minRange(arr, n, k);
// This code is contributed by rag2127
</script>
Producción
5 7
Complejidad de tiempo: O(N) , donde N es el número de elementos en la array. En el peor de los casos, cada elemento se agregará una vez y se eliminará una vez del mapa.
Complejidad espacial: O(K), en el peor de los casos, solo podemos tener elementos ‘K’ en nuestro mapa.
Este artículo es una contribución de Rajdeep Mallick . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA