Dado un arreglo arr[] que consta de N enteros y un entero positivo K , la tarea es contar el número de subarreglos que tienen exactamente K elementos que ocurren al menos dos veces .
Ejemplos:
Entrada: arr[] = {1, 1, 1, 2, 2}, K = 1
Salida: 7
Explicación: Los subarreglos que tienen exactamente 1 elemento que aparece al menos dos veces son:
- {1, 1}. La frecuencia de 1 es 2.
- {1, 1, 1}. La frecuencia de 1 es 3.
- {1, 1, 1, 2}. La frecuencia de 1 es 3.
- {1, 1}. La frecuencia de 1 es 2.
- {1, 1, 2}. La frecuencia de 1 es 2.
- {1, 2, 2}. La frecuencia de 2 es 2.
- {2, 2}. La frecuencia de 2 es 2.
Por lo tanto, la salida requerida es 7.
Entrada: arr[] = {1, 2, 1, 2, 3}, K = 3
Salida: 0
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todos los subarreglos posibles a partir del arreglo dado y contar esos subarreglos que tienen exactamente K elementos que ocurren al menos dos veces . Después de haber verificado todos los subarreglos , imprima el número total de subarreglos obtenidos.
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de la técnica Hashing y Two pointers . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos cntSub como 0 , para almacenar el recuento de todos los subarreglos posibles que tengan exactamente K elementos que aparezcan al menos dos veces .
- Inicialice dos variables, digamos l como 0 y r como 0 , para almacenar los índices de los límites izquierdo y derecho de cada subarreglo, respectivamente.
- Inicialice un Map , digamos mp , y un Set , digamos S para almacenar el conteo de elementos en los subarreglos y almacene los elementos cuya frecuencia en el subarreglo sea al menos 2 respectivamente.
- Iterar hasta que r sea menor que N y realizar las siguientes operaciones:
- Iterar mientras r es menor que N y el tamaño del conjunto es como máximo K :
- Incremente el conteo de arr[r] en mp y luego empuje el elemento al conjunto S si mp[arr[r]] es igual a 2 .
- Incremente r en 1 .
- Si el tamaño del conjunto S es K , incremente cntSub en 1 .
- Iterar mientras l < r y el tamaño del conjunto es mayor que K :
- Disminuya el conteo de arr[l] en mp y luego borre el elemento del conjunto S si mp[arr[r]] es igual a 1 .
- Incremente cntSub y l en 1 .
- Iterar mientras r es menor que N y el tamaño del conjunto es como máximo K :
- Ahora itere mientras l < N y el tamaño del conjunto es K y disminuya el conteo de arr[l] en 1 y si la frecuencia de arr[l] es 1 , entonces borre el arr[l] del conjunto.
- Después de completar los pasos anteriores, imprima el valor de cntSub como el recuento resultante de subarreglos.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the subarrays with
// exactly K elements occurring twice
int cntSubarrays(int A[], int K, int n)
{
// Stores the count of subarrays
// having exactly K elements
// occurring at least twice
int cntSub = 0;
// Stores the count of
// integers in the subarray
map<int, int> mp;
// Stores the indices of left
// boundary and right boundary
int l = 0, r = 0;
// Store the elements which occurs
// atleast twice between [l, r]
set<int> st;
// Iterate while r < n
while (r < n) {
// Iterate while r < n
// and size of st <= K
while (r < n && st.size() <= K) {
// If mp[A[r]] >= 1
if (mp[A[r]]) {
st.insert(A[r]);
}
// Increment count of A[r]
mp[A[r]]++;
// Increment r by 1
r++;
// If st.size() is K
if (st.size() == K)
cntSub++;
}
// Iterate while l < r
// and st.size() > K
while (l < r && st.size() > K) {
// Increment cntSub by 1
cntSub++;
// Decrement cntSub by 1
mp[A[l]]--;
// If mp[A[l]] = 1
if (mp[A[l]] == 1) {
st.erase(st.find(A[l]));
}
// Increment l by 1
l++;
}
}
// Iterate while l < n and
// st.size() == K
while (l < n && st.size() == K) {
// Increment cntSub by 1
cntSub++;
mp[A[l]]--;
// If Mp[A[l]] is equal to 1
if (mp[A[l]] == 1) {
st.erase(st.find(A[l]));
}
// Increment l by 1
l++;
}
// Return cntSub
return cntSub;
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 1, 2, 2 };
int K = 1;
int N = sizeof(arr) / sizeof(arr[0]);
cout << cntSubarrays(arr, K, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to count the subarrays with
// exactly K elements occurring twice
static int cntSubarrays(int[] A, int K, int n)
{
// Stores the count of subarrays
// having exactly K elements
// occurring at least twice
int cntSub = 0;
// Stores the count of
// integers in the subarray
HashMap<Integer, Integer> mp
= new HashMap<Integer, Integer>();
// Stores the indices of left
// boundary and right boundary
int l = 0, r = 0;
// Store the elements which occurs
// atleast twice between [l, r]
HashSet<Integer> st = new HashSet<Integer>();
// Iterate while r < n
while (r < n) {
// Iterate while r < n
// and size of st <= K
while (r < n && st.size() <= K) {
// If mp[A[r]] >= 1
if (mp.containsKey(A[r])) {
st.add(A[r]);
}
// Increment count of A[r]
if (mp.containsKey(A[r]))
mp.put(A[r], mp.get(A[r]) + 1);
else
mp.put(A[r], 1);
// Increment r by 1
r++;
// If st.size() is K
if (st.size() == K)
cntSub++;
}
// Iterate while l < r
// and st.size() > K
while (l < r && st.size() > K) {
// Increment cntSub by 1
cntSub++;
// Decrement cntSub by 1
if (mp.containsKey(A[l]))
mp.put(A[l], mp.get(A[l]) - 1);
// If mp[A[l]] = 1
if (mp.get(A[l]) == 1) {
st.remove(A[l]);
}
// Increment l by 1
l++;
}
}
// Iterate while l < n and
// st.size() == K
while (l < n && st.size() == K) {
// Increment cntSub by 1
cntSub++;
if (mp.containsKey(A[l]))
mp.put(A[l], mp.get(A[l]) - 1);
// If Mp[A[l]] is equal to 1
if (mp.get(A[l]) == 1) {
st.remove(A[l]);
}
// Increment l by 1
l++;
}
// Return cntSub
return cntSub;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 1, 1, 2, 2 };
int K = 1;
int N = arr.length;
System.out.println(cntSubarrays(arr, K, N));
}
}
// This code is contributed by ukasp.
Python3
# Python3 program for the above approach
# Function to count the subarrays with
# exactly K elements occurring twice
def cntSubarrays(A, K, n):
# Stores the count of subarrays
# having exactly K elements
# occurring at least twice
cntSub = 0
# Stores the count of
# integers in the subarray
mp = {}
# Stores the indices of left
# boundary and right boundary
l = 0
r = 0
# Store the elements which occurs
# atleast twice between [l, r]
st = set()
# Iterate while r < n
while (r < n):
# Iterate while r < n
# and size of st <= K
while (r < n and len(st) <= K):
# If mp[A[r]] >= 1
if (A[r] in mp):
st.add(A[r])
# Increment count of A[r]
if (A[r] in mp):
mp[A[r]] += 1
else:
mp[A[r]] = 1
# Increment r by 1
r += 1
# If st.size() is K
if (len(st) == K):
cntSub += 1
# Iterate while l < r
# and st.size() > K
while (l < r and len(st) > K):
# Increment cntSub by 1
cntSub += 1
# Decrement cntSub by 1
if (A[l] in mp):
mp[A[l]] -= 1
else:
mp[A[l]] = 1
# If mp[A[l]] = 1
if (mp[A[l]] == 1):
st.remove(A[l])
# Increment l by 1
l += 1
# Iterate while l < n and
# st.size() == K
while (l < n and len(st) == K):
# Increment cntSub by 1
cntSub += 1
mp[A[l]] -= 1
# If Mp[A[l]] is equal to 1
if (mp[A[l]] == 1):
st.remove(A[l])
# Increment l by 1
l += 1
# Return cntSub
return cntSub
# Driver Code
if __name__ == '__main__':
arr = [1, 1, 1, 2, 2]
K = 1
N = len(arr)
print(cntSubarrays(arr, K, N))
# This code is contributed by ipg2016107
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to count the subarrays with
// exactly K elements occurring twice
static int cntSubarrays(int []A, int K, int n)
{
// Stores the count of subarrays
// having exactly K elements
// occurring at least twice
int cntSub = 0;
// Stores the count of
// integers in the subarray
Dictionary<int,int> mp = new Dictionary<int,int>();
// Stores the indices of left
// boundary and right boundary
int l = 0, r = 0;
// Store the elements which occurs
// atleast twice between [l, r]
HashSet<int> st = new HashSet<int>();
// Iterate while r < n
while (r < n) {
// Iterate while r < n
// and size of st <= K
while (r < n && st.Count <= K) {
// If mp[A[r]] >= 1
if (mp.ContainsKey(A[r])) {
st.Add(A[r]);
}
// Increment count of A[r]
if (mp.ContainsKey(A[r]))
mp[A[r]]++;
else
mp[A[r]] = 1;
// Increment r by 1
r++;
// If st.size() is K
if (st.Count == K)
cntSub++;
}
// Iterate while l < r
// and st.size() > K
while (l < r && st.Count > K) {
// Increment cntSub by 1
cntSub++;
// Decrement cntSub by 1
if (mp.ContainsKey(A[l]))
mp[A[l]]--;
// If mp[A[l]] = 1
if (mp[A[l]] == 1) {
st.Remove(A[l]);
}
// Increment l by 1
l++;
}
}
// Iterate while l < n and
// st.size() == K
while (l < n && st.Count == K) {
// Increment cntSub by 1
cntSub++;
if (mp.ContainsKey(A[l]))
mp[A[l]]--;
// If Mp[A[l]] is equal to 1
if (mp[A[l]] == 1) {
st.Remove(A[l]);
}
// Increment l by 1
l++;
}
// Return cntSub
return cntSub;
}
// Driver Code
public static void Main()
{
int []arr = { 1, 1, 1, 2, 2 };
int K = 1;
int N = arr.Length;
Console.WriteLine(cntSubarrays(arr, K, N));
}
}
// This code is contributed by ipg2016107.
Javascript
<script>
// JavaScript program for the above approach
// Function to count the subarrays with
// exactly K elements occurring twice
function cntSubarrays(A,K,n)
{
// Stores the count of subarrays
// having exactly K elements
// occurring at least twice
let cntSub = 0;
// Stores the count of
// integers in the subarray
let mp = new Map();
// Stores the indices of left
// boundary and right boundary
let l = 0, r = 0;
// Store the elements which occurs
// atleast twice between [l, r]
let st = new Set();
// Iterate while r < n
while (r < n) {
// Iterate while r < n
// and size of st <= K
while (r < n && st.size <= K) {
// If mp[A[r]] >= 1
if (mp.has(A[r])) {
st.add(A[r]);
}
// Increment count of A[r]
if (mp.has(A[r]))
mp.set(A[r], mp.get(A[r]) + 1);
else
mp.set(A[r], 1);
// Increment r by 1
r++;
// If st.size() is K
if (st.size == K)
cntSub++;
}
// Iterate while l < r
// and st.size() > K
while (l < r && st.size > K) {
// Increment cntSub by 1
cntSub++;
// Decrement cntSub by 1
if (mp.has(A[l]))
mp.set(A[l], mp.get(A[l]) - 1);
// If mp[A[l]] = 1
if (mp.get(A[l]) == 1) {
st.delete(A[l]);
}
// Increment l by 1
l++;
}
}
// Iterate while l < n and
// st.size() == K
while (l < n && st.size == K) {
// Increment cntSub by 1
cntSub++;
if (mp.has(A[l]))
mp.set(A[l], mp.get(A[l]) - 1);
// If Mp[A[l]] is equal to 1
if (mp.get(A[l]) == 1) {
st.delete(A[l]);
}
// Increment l by 1
l++;
}
// Return cntSub
return cntSub;
}
// Driver Code
let arr=[1, 1, 1, 2, 2 ];
let K = 1;
let N = arr.length;
document.write(cntSubarrays(arr, K, N));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
7
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)