Dada una array de n enteros. Cuente el número total de subarreglos que tienen un total de elementos distintos, igual que el total de elementos distintos del arreglo original.
Ejemplos:
Input : arr[] = {2, 1, 3, 2, 3}
Output : 5
Total distinct elements in array is 3
Total sub-arrays that satisfy the condition
are: Subarray from index 0 to 2
Subarray from index 0 to 3
Subarray from index 0 to 4
Subarray from index 1 to 3
Subarray from index 1 to 4
Input : arr[] = {2, 4, 5, 2, 1}
Output : 2
Input : arr[] = {2, 4, 4, 2, 4}
Output : 9
Un enfoque ingenuo es ejecutar un ciclo uno dentro de otro y considerar todos los subconjuntos y, para cada subconjunto, contar todos los elementos distintos mediante el uso de hashing y compararlos con el total de elementos distintos del conjunto original. Este enfoque requiere un tiempo O(n 2 ).
Un enfoque eficiente es usar una ventana deslizante para contar todos los elementos distintos en una iteración.
- Encuentre el número de elementos distintos en la array completa. Sea este número k <= N . Inicializar Izquierda = 0, Derecha = 0 y ventana = 0.
- Incremente a la derecha hasta que el número de elementos distintos en el rango [Izquierda=0, Derecha] sea igual a k (o el tamaño de la ventana no sería igual a k), deje que este derecho sea R 1 . Ahora, dado que el subconjunto [Left = 0, R 1 ] tiene k elementos distintos, todos los subconjuntos que comienzan en Left = 0 y terminan después de R 1 también tendrán k elementos distintos. Por lo tanto, agregue NR 1 +1 a la respuesta porque [Izquierda.. R 1 ], [Izquierda.. R 1 +1], [Izquierda.. R 1 +2] … [Izquierda.. N-1]contiene todos los números distintos.
- Ahora manteniendo R 1 igual, incremente a la izquierda . Disminuya la frecuencia del elemento anterior, es decir, arr[0], y si su frecuencia se convierte en 0, disminuya el tamaño de la ventana. Ahora, el subconjunto es [Left = 1, Right = R 1 ] .
- Repita el mismo proceso desde el paso 2 para otros valores de Left y Right hasta Left < N .
Implementación:
C++
// C++ program Count total number of sub-arrays
// having total distinct elements same as that
// original array.
#include<bits/stdc++.h>
using namespace std;
// Function to calculate distinct sub-array
int countDistictSubarray(int arr[], int n)
{
// Count distinct elements in whole array
unordered_map<int, int> vis;
for (int i = 0; i < n; ++i)
vis[arr[i]] = 1;
int k = vis.size();
// Reset the container by removing all elements
vis.clear();
// Use sliding window concept to find
// count of subarrays having k distinct
// elements.
int ans = 0, right = 0, window = 0;
for (int left = 0; left < n; ++left)
{
while (right < n && window < k)
{
++vis[ arr[right] ];
if (vis[ arr[right] ] == 1)
++window;
++right;
}
// If window size equals to array distinct
// element size, then update answer
if (window == k)
ans += (n - right + 1);
// Decrease the frequency of previous element
// for next sliding window
--vis[ arr[left] ];
// If frequency is zero then decrease the
// window size
if (vis[ arr[left] ] == 0)
--window;
}
return ans;
}
// Driver code
int main()
{
int arr[] = {2, 1, 3, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
cout << countDistictSubarray(arr, n) <<"n";
return 0;
}
Java
// Java program Count total number of sub-arrays
// having total distinct elements same as that
// original array.
import java.util.HashMap;
class Test
{
// Method to calculate distinct sub-array
static int countDistictSubarray(int arr[], int n)
{
// Count distinct elements in whole array
HashMap<Integer, Integer> vis = new HashMap<Integer,Integer>(){
@Override
public Integer get(Object key) {
if(!containsKey(key))
return 0;
return super.get(key);
}
};
for (int i = 0; i < n; ++i)
vis.put(arr[i], 1);
int k = vis.size();
// Reset the container by removing all elements
vis.clear();
// Use sliding window concept to find
// count of subarrays having k distinct
// elements.
int ans = 0, right = 0, window = 0;
for (int left = 0; left < n; ++left)
{
while (right < n && window < k)
{
vis.put(arr[right], vis.get(arr[right]) + 1);
if (vis.get(arr[right])== 1)
++window;
++right;
}
// If window size equals to array distinct
// element size, then update answer
if (window == k)
ans += (n - right + 1);
// Decrease the frequency of previous element
// for next sliding window
vis.put(arr[left], vis.get(arr[left]) - 1);
// If frequency is zero then decrease the
// window size
if (vis.get(arr[left]) == 0)
--window;
}
return ans;
}
// Driver method
public static void main(String args[])
{
int arr[] = {2, 1, 3, 2, 3};
System.out.println(countDistictSubarray(arr, arr.length));
}
}
Python3
# Python3 program Count total number of # sub-arrays having total distinct elements # same as that original array. # Function to calculate distinct sub-array def countDistictSubarray(arr, n): # Count distinct elements in whole array vis = dict() for i in range(n): vis[arr[i]] = 1 k = len(vis) # Reset the container by removing # all elements vid = dict() # Use sliding window concept to find # count of subarrays having k distinct # elements. ans = 0 right = 0 window = 0 for left in range(n): while (right < n and window < k): if arr[right] in vid.keys(): vid[ arr[right] ] += 1 else: vid[ arr[right] ] = 1 if (vid[ arr[right] ] == 1): window += 1 right += 1 # If window size equals to array distinct # element size, then update answer if (window == k): ans += (n - right + 1) # Decrease the frequency of previous # element for next sliding window vid[ arr[left] ] -= 1 # If frequency is zero then decrease # the window size if (vid[ arr[left] ] == 0): window -= 1 return ans # Driver code arr = [2, 1, 3, 2, 3] n = len(arr) print(countDistictSubarray(arr, n)) # This code is contributed by # mohit kumar 29
C#
// C# program Count total number of sub-arrays
// having total distinct elements same as that
// original array.
using System;
using System.Collections.Generic;
class Test
{
// Method to calculate distinct sub-array
static int countDistictSubarray(int []arr, int n)
{
// Count distinct elements in whole array
Dictionary<int, int> vis = new Dictionary<int,int>();
for (int i = 0; i < n; ++i)
if(!vis.ContainsKey(arr[i]))
vis.Add(arr[i], 1);
int k = vis.Count;
// Reset the container by removing all elements
vis.Clear();
// Use sliding window concept to find
// count of subarrays having k distinct
// elements.
int ans = 0, right = 0, window = 0;
for (int left = 0; left < n; ++left)
{
while (right < n && window < k)
{
if(vis.ContainsKey(arr[right]))
vis[arr[right]] = vis[arr[right]] + 1;
else
vis.Add(arr[right], 1);
if (vis[arr[right]] == 1)
++window;
++right;
}
// If window size equals to array distinct
// element size, then update answer
if (window == k)
ans += (n - right + 1);
// Decrease the frequency of previous element
// for next sliding window
if(vis.ContainsKey(arr[left]))
vis[arr[left]] = vis[arr[left]] - 1;
// If frequency is zero then decrease the
// window size
if (vis[arr[left]] == 0)
--window;
}
return ans;
}
// Driver method
public static void Main(String []args)
{
int []arr = {2, 1, 3, 2, 3};
Console.WriteLine(countDistictSubarray(arr, arr.Length));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program Count total number of sub-arrays
// having total distinct elements same as that
// original array.
// Method to calculate distinct sub-array
function countDistictSubarray(arr,n)
{
// Count distinct elements in whole array
let vis = new Map();
for (let i = 0; i < n; ++i)
vis.set(arr[i], 1);
let k = vis.size;
// Reset the container by removing all elements
let vid=new Map();
// Use sliding window concept to find
// count of subarrays having k distinct
// elements.
let ans = 0, right = 0, window = 0;
for (let left = 0; left < n; left++)
{
while (right < n && window < k)
{
if(vid.has(arr[right]))
vid.set(arr[right], vid.get(arr[right]) + 1);
else
vid.set(arr[right], 1);
if (vid.get(arr[right])== 1)
window++;
right++;
}
// If window size equals to array distinct
// element size, then update answer
if (window == k)
ans += (n - right + 1);
// Decrease the frequency of previous element
// for next sliding window
if(vid.has(arr[left]))
vid.set(arr[left], vid.get(arr[left])- 1);
// If frequency is zero then decrease the
// window size
if (vid.get(arr[left]) == 0)
--window;
}
return ans;
}
// Driver method
let arr=[2, 1, 3, 2, 3];
document.write(countDistictSubarray(arr, arr.length));
// This code is contributed by patel2127
</script>
Producción
5n
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Shubham Bansal . 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