Dada una array arr[] de tamaño N y un entero K . La tarea es encontrar el recuento de subarreglos de modo que cada subarreglo tenga exactamente K elementos distintos.
Ejemplos:
Entrada: arr[] = {2, 1, 2, 1, 6}, K = 2
Salida: 7
{2, 1}, {1, 2}, {2, 1}, {1, 6}, {2 , 1, 2},
{1, 2, 1} y {2, 1, 2, 1} son los únicos subarreglos válidos.Entrada: arr[] = {1, 2, 3, 4, 5}, K = 1
Salida: 5
Enfoque: Contar directamente los subarreglos con exactamente K enteros diferentes es difícil, pero encontrar el conteo de subarreglos con como máximo K enteros diferentes es fácil. Entonces, la idea es encontrar el recuento de subarreglos con un máximo de K enteros diferentes, sea C(K) , y el recuento de subarreglos con un máximo de (K – 1) enteros diferentes, sea C(K – 1) y finalmente tome su diferencia, C(K) – C(K – 1) que es la respuesta requerida.
El recuento de subarreglos con un máximo de K elementos diferentes se puede calcular fácilmente mediante la técnica de la ventana deslizante. La idea es seguir expandiendo el límite derecho de la ventana hasta que el recuento de elementos distintos en la ventana sea menor o igual a K y cuando el recuento de elementos distintos dentro de la ventana sea mayor que K , comience a reducir la ventana desde la izquierda. hasta que el conteo sea menor o igual a K . Además, para cada expansión, siga contando los subarreglos como derecha – izquierda + 1 , donde derecha e izquierda son los límites de la ventana actual.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include<bits/stdc++.h>
#include<map>
using namespace std;
// Function to return the count of subarrays
// with at most K distinct elements using
// the sliding window technique
int atMostK(int arr[], int n, int k)
{
// To store the result
int count = 0;
// Left boundary of window
int left = 0;
// Right boundary of window
int right = 0;
// Map to keep track of number of distinct
// elements in the current window
unordered_map<int,int> map;
// Loop to calculate the count
while (right < n) {
// Calculating the frequency of each
// element in the current window
if (map.find(arr[right])==map.end())
map[arr[right]]=0;
map[arr[right]]++;
// Shrinking the window from left if the
// count of distinct elements exceeds K
while (map.size() > k) {
map[arr[left]]= map[arr[left]] - 1;
if (map[arr[left]] == 0)
map.erase(arr[left]);
left++;
}
// Adding the count of subarrays with at most
// K distinct elements in the current window
count += right - left + 1;
right++;
}
return count;
}
// Function to return the count of subarrays
// with exactly K distinct elements
int exactlyK(int arr[], int n, int k)
{
// Count of subarrays with exactly k distinct
// elements is equal to the difference of the
// count of subarrays with at most K distinct
// elements and the count of subararys with
// at most (K - 1) distinct elements
return (atMostK(arr, n, k) - atMostK(arr, n, k - 1));
}
// Driver code
int main()
{
int arr[] = { 2, 1, 2, 1, 6 };
int n = sizeof(arr)/sizeof(arr[0]);
int k = 2;
cout<<(exactlyK(arr, n, k));
}
Java
// Java implementation of the approach
import java.util.*;
public class GfG {
// Function to return the count of subarrays
// with at most K distinct elements using
// the sliding window technique
private static int atMostK(int arr[], int n, int k)
{
// To store the result
int count = 0;
// Left boundary of window
int left = 0;
// Right boundary of window
int right = 0;
// Map to keep track of number of distinct
// elements in the current window
HashMap<Integer, Integer> map = new HashMap<>();
// Loop to calculate the count
while (right < n) {
// Calculating the frequency of each
// element in the current window
map.put(arr[right],
map.getOrDefault(arr[right], 0) + 1);
// Shrinking the window from left if the
// count of distinct elements exceeds K
while (map.size() > k) {
map.put(arr[left], map.get(arr[left]) - 1);
if (map.get(arr[left]) == 0)
map.remove(arr[left]);
left++;
}
// Adding the count of subarrays with at most
// K distinct elements in the current window
count += right - left + 1;
right++;
}
return count;
}
// Function to return the count of subarrays
// with exactly K distinct elements
private static int exactlyK(int arr[], int n, int k)
{
// Count of subarrays with exactly k distinct
// elements is equal to the difference of the
// count of subarrays with at most K distinct
// elements and the count of subararys with
// at most (K - 1) distinct elements
return (atMostK(arr, n, k)
- atMostK(arr, n, k - 1));
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 1, 2, 1, 6 };
int n = arr.length;
int k = 2;
System.out.print(exactlyK(arr, n, k));
}
}
Python3
# Python3 implementation of the above approach
# Function to return the count of subarrays
# with at most K distinct elements using
# the sliding window technique
def atMostK(arr, n, k):
# To store the result
count = 0
# Left boundary of window
left = 0
# Right boundary of window
right = 0
# Map to keep track of number of distinct
# elements in the current window
map = {}
# Loop to calculate the count
while(right < n):
if arr[right] not in map:
map[arr[right]] = 0
# Calculating the frequency of each
# element in the current window
map[arr[right]] += 1
# Shrinking the window from left if the
# count of distinct elements exceeds K
while(len(map) > k):
if arr[left] not in map:
map[arr[left]] = 0
map[arr[left]] -= 1
if map[arr[left]] == 0:
del map[arr[left]]
left += 1
# Adding the count of subarrays with at most
# K distinct elements in the current window
count += right - left + 1
right += 1
return count
# Function to return the count of subarrays
# with exactly K distinct elements
def exactlyK(arr, n, k):
# Count of subarrays with exactly k distinct
# elements is equal to the difference of the
# count of subarrays with at most K distinct
# elements and the count of subararys with
# at most (K - 1) distinct elements
return (atMostK(arr, n, k) -
atMostK(arr, n, k - 1))
# Driver code
if __name__ == "__main__":
arr = [2, 1, 2, 1, 6]
n = len(arr)
k = 2
print(exactlyK(arr, n, k))
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GfG {
// Function to return the count of subarrays
// with at most K distinct elements using
// the sliding window technique
private static int atMostK(int[] arr, int n, int k)
{
// To store the result
int count = 0;
// Left boundary of window
int left = 0;
// Right boundary of window
int right = 0;
// Map to keep track of number of distinct
// elements in the current window
Dictionary<int, int> map
= new Dictionary<int, int>();
// Loop to calculate the count
while (right < n) {
// Calculating the frequency of each
// element in the current window
if (map.ContainsKey(arr[right]))
map[arr[right]] = map[arr[right]] + 1;
else
map.Add(arr[right], 1);
// Shrinking the window from left if the
// count of distinct elements exceeds K
while (map.Count > k) {
if (map.ContainsKey(arr[left])) {
map[arr[left]] = map[arr[left]] - 1;
if (map[arr[left]] == 0)
map.Remove(arr[left]);
}
left++;
}
// Adding the count of subarrays with at most
// K distinct elements in the current window
count += right - left + 1;
right++;
}
return count;
}
// Function to return the count of subarrays
// with exactly K distinct elements
private static int exactlyK(int[] arr, int n, int k)
{
// Count of subarrays with exactly k distinct
// elements is equal to the difference of the
// count of subarrays with at most K distinct
// elements and the count of subararys with
// at most (K - 1) distinct elements
return (atMostK(arr, n, k)
- atMostK(arr, n, k - 1));
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 2, 1, 2, 1, 6 };
int n = arr.Length;
int k = 2;
Console.Write(exactlyK(arr, n, k));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Function to return the count of subarrays
// with at most K distinct elements using
// the sliding window technique
function atMostK(arr, n, k)
{
// To store the result
let count = 0;
// Left boundary of window
let left = 0;
// Right boundary of window
let right = 0;
// Map to keep track of number of distinct
// elements in the current window
let map = new Map();
// Loop to calculate the count
while (right < n)
{
// Calculating the frequency of each
// element in the current window
if (map.has(arr[right]))
map.set(arr[right],
map.get(arr[right]) + 1);
else
map.set(arr[right], 1);
// Shrinking the window from left if the
// count of distinct elements exceeds K
while (map.size > k)
{
map.set(arr[left], map.get(arr[left]) - 1);
if (map.get(arr[left]) == 0)
map.delete(arr[left]);
left++;
}
// Adding the count of subarrays with at most
// K distinct elements in the current window
count += right - left + 1;
right++;
}
return count;
}
// Function to return the count of subarrays
// with exactly K distinct elements
function exactlyK(arr, n, k)
{
// Count of subarrays with exactly k distinct
// elements is equal to the difference of the
// count of subarrays with at most K distinct
// elements and the count of subararys with
// at most (K - 1) distinct elements
return (atMostK(arr, n, k) -
atMostK(arr, n, k - 1));
}
// Driver code
let arr = [ 2, 1, 2, 1, 6 ];
let n = arr.length;
let k = 2;
document.write(exactlyK(arr, n, k));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
7
Complejidad temporal: O(N)
Complejidad espacial: O(N)
Otro enfoque: cuando mueva el cursor derecho, siga rastreando si hemos llegado a un conteo de K enteros distintos, en caso afirmativo, procesamos el cursor izquierdo, así es como procesamos el cursor izquierdo:
- comprobar si el elemento apuntado por el cursor izquierdo está duplicado en la ventana, en caso afirmativo, lo eliminamos, y usamos una variable (por ejemplo, prefijo) para registrar que hemos eliminado un elemento de la ventana). mantenga este proceso hasta que reduzcamos el tamaño de la ventana exactamente a K. ahora podemos calcular el número de la array buena válida como prefijo res +=;
- después de procesar el cursor izquierdo y todas las cosas, el bucle externo continuará y el cursor derecho avanzará, y luego el tamaño de la ventana excederá K, simplemente podemos soltar el elemento más a la izquierda de la ventana y restablecer el prefijo a 0. y continuar .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to calculate number
// of subarrays with distinct elements of size k
#include <bits/stdc++.h>
#include <map>
#include <vector>
using namespace std;
int subarraysWithKDistinct(vector<int>& A, int K)
{
// declare a map for the frequency
unordered_map<int, int> mapp;
int begin = 0, end = 0, prefix = 0, cnt = 0;
int res = 0;
// traverse the array
while (end < A.size())
{
// increase the frequency
mapp[A[end]]++;
if (mapp[A[end]] == 1) {
cnt++;
}
end++;
if (cnt > K)
{
mapp[A[begin]]--;
begin++;
cnt--;
prefix = 0;
}
// loop until mapp[A[begin]] > 1
while (mapp[A[begin]] > 1)
{
mapp[A[begin]]--;
begin++;
prefix++;
}
if (cnt == K)
{
res += prefix + 1;
}
}
// return the final count
return res;
}
// Driver code
int main()
{
vector<int> arr{ 2, 1, 2, 1, 6 };
int k = 2;
// Function call
cout << (subarraysWithKDistinct(arr, k));
}
// This code is contributed by Harman Singh
Java
// Java program to calculate number
// of subarrays with distinct elements of size k
import java.util.*;
class GFG
{
static int subarraysWithKDistinct(int A[], int K)
{
// declare a map for the frequency
HashMap<Integer, Integer> mapp = new HashMap<>();
int begin = 0, end = 0, prefix = 0, cnt = 0;
int res = 0;
// traverse the array
while (end < A.length)
{
// increase the frequency
if(mapp.containsKey(A[end]))
{
mapp.put(A[end], mapp.get(A[end]) + 1);
}
else
{
mapp.put(A[end], 1);
}
if (mapp.get(A[end]) == 1)
{
cnt++;
}
end++;
if (cnt > K)
{
if(mapp.containsKey(A[begin]))
{
mapp.put(A[begin], mapp.get(A[begin]) - 1);
}
else
{
mapp.put(A[begin], -1);
}
begin++;
cnt--;
prefix = 0;
}
// loop until mapp[A[begin]] > 1
while (mapp.get(A[begin]) > 1)
{
if(mapp.containsKey(A[begin]))
{
mapp.put(A[begin], mapp.get(A[begin]) - 1);
}
else
{
mapp.put(A[begin], -1);
}
begin++;
prefix++;
}
if (cnt == K)
{
res += prefix + 1;
}
}
// return the final count
return res;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 2, 1, 2, 1, 6 };
int k = 2;
// Function call
System.out.println(subarraysWithKDistinct(arr, k));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program to calculate number of
# subarrays with distinct elements of size k
def subarraysWithKDistinct(A, K):
# Declare a map for the frequency
mapp = {}
begin, end, prefix, cnt = 0, 0, 0, 0
res = 0
# Traverse the array
while (end < len(A)):
# Increase the frequency
mapp[A[end]] = mapp.get(A[end], 0) + 1
if (mapp[A[end]] == 1):
cnt += 1
end += 1
if (cnt > K):
mapp[A[begin]] -= 1
begin += 1
cnt -= 1
prefix = 0
# Loop until mapp[A[begin]] > 1
while (mapp[A[begin]] > 1):
mapp[A[begin]] -= 1
begin += 1
prefix += 1
if (cnt == K):
res += prefix + 1
# Return the final count
return res
# Driver code
if __name__ == '__main__':
arr = [ 2, 1, 2, 1, 6 ]
k = 2
# Function call
print (subarraysWithKDistinct(arr, k))
# This code is contributed by Mohit kumar
C#
// C# program to calculate number
// of subarrays with distinct elements of size k
using System;
using System.Collections.Generic;
class GFG {
static int subarraysWithKDistinct(List<int> A, int K)
{
// declare a map for the frequency
Dictionary<int, int> mapp = new Dictionary<int, int>();
int begin = 0, end = 0, prefix = 0, cnt = 0;
int res = 0;
// traverse the array
while (end < A.Count)
{
// increase the frequency
if(mapp.ContainsKey(A[end]))
{
mapp[A[end]]++;
}
else{
mapp[A[end]] = 1;
}
if (mapp[A[end]] == 1) {
cnt++;
}
end++;
if (cnt > K)
{
if(mapp.ContainsKey(A[begin]))
{
mapp[A[begin]]--;
}
else{
mapp[A[begin]] = -1;
}
begin++;
cnt--;
prefix = 0;
}
// loop until mapp[A[begin]] > 1
while (mapp[A[begin]] > 1)
{
mapp[A[begin]]--;
begin++;
prefix++;
}
if (cnt == K)
{
res += prefix + 1;
}
}
// return the final count
return res;
}
// Driver code
static void Main()
{
List<int> arr = new List<int>(new int[] { 2, 1, 2, 1, 6 });
int k = 2;
// Function call
Console.Write(subarraysWithKDistinct(arr, k));
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript program to calculate number
// of subarrays with distinct elements of size k
function subarraysWithKDistinct(A, K)
{
// Declare a map for the frequency
let mapp = new Map();
let begin = 0, end = 0, prefix = 0, cnt = 0;
let res = 0;
// Traverse the array
while (end < A.length)
{
// increase the frequency
if (mapp.has(A[end]))
{
mapp.set(A[end],
mapp.get(A[end]) + 1);
}
else
{
mapp.set(A[end], 1);
}
if (mapp.get(A[end]) == 1)
{
cnt++;
}
end++;
if (cnt > K)
{
if (mapp.has(A[begin]))
{
mapp.set(A[begin],
mapp.get(A[begin]) - 1);
}
else
{
mapp.set(A[begin], -1);
}
begin++;
cnt--;
prefix = 0;
}
// loop until mapp[A[begin]] > 1
while (mapp.get(A[begin]) > 1)
{
if(mapp.has(A[begin]))
{
mapp.set(A[begin],
mapp.get(A[begin]) - 1);
}
else
{
mapp.set(A[begin], -1);
}
begin++;
prefix++;
}
if (cnt == K)
{
res += prefix + 1;
}
}
// Return the final count
return res;
}
// Driver code
let arr = [ 2, 1, 2, 1, 6 ];
let k = 2;
// Function call
document.write(subarraysWithKDistinct(arr, k));
// This code is contributed by rag2127
</script>
Producción
7
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ishan_trivedi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA