Dado un arreglo de N enteros y un número M. La tarea es encontrar el número máximo de enteros únicos entre todos los posibles subarreglos contiguos de tamaño M.
Ejemplos :
Entrada : arr[] = {5, 3, 5, 2, 3, 2}, M = 3
Salida : 3
Explicación :
en el caso de prueba de ejemplo, hay 4 subarreglos de tamaño 3.
s1 = (5, 3, 5 )- Tiene 2 números únicos.
s2 = (3, 5, 2)- Tiene 3 números únicos.
s3 = (5, 2, 3)- Tiene 3 números únicos.
s4 = (2, 3, 2)- Tiene 2 números únicos.
En estos subarreglos, hay 2, 3, 3, 2 números únicos, respectivamente.
La cantidad máxima de números únicos entre todos los subarreglos contiguos posibles es 3.Entrada : arr[] = {5, 5, 5, 5, 5, 5}, M = 3
Salida : 1
Enfoque ingenuo :
- Genere todos los subarreglos de tamaño M.
- Cuente un número único para cada subarreglo.
- Compruebe si es mayor que el número único máximo anterior o no, en caso afirmativo, reemplácelo con el número único máximo anterior.
- Continúe hasta que generemos todos los subarreglos posibles.
A continuación se muestra la implementación del enfoque anterior:
C++
// A C++ programme to find maximum distinct elements
// in a subarray of size k
#include<bits/stdc++.h>
using namespace std;
//Function to find maximum unique element in
//a subarray of size k
int maxUniqueNum(int a[],int N,int M)
{
int maxUnique=0;
//search every subarray of size k
//and find how many unique element present
for(int i=0;i<=N-M;i++)
{
//create an empty set to store the unique elements
set<int> s;
for(int j=0;j<M;j++)
{
//insert all elements
//duplicate elements are not stored in set
s.insert(a[i+j]);
}
//update the maxUnique
if(s.size()>maxUnique)
{
maxUnique=s.size();
}
}
return maxUnique;
}
int main()
{
int arr[] = {5, 3, 5, 2, 3, 2};
int M=3,N=sizeof(arr)/sizeof(arr[0]);
cout<<maxUniqueNum(arr,N,M)<<endl;
}
Java
// Java Program to find maximum number of
// Unique integers in Sub-Array
// of given size
import java.util.*;
class GFG {
// Function to find maximum number of
// Unique integers in Sub-Array
// of given size
public static int maxUniqueNum(int arr[],
int N, int M)
{
int maxUnique = 0;
// Generate all subarrays of size M
for (int i = 0; i <= N - M; i++) {
int currentUnique = 0;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int k = i; k < i + M; k++) {
// if the key is new to the map,
// push the key in map and increment
// count for unique number
if (!map.containsKey(arr[k])) {
map.put(arr[i], 1);
currentUnique++;
}
}
if (currentUnique > maxUnique)
maxUnique = currentUnique;
}
return maxUnique;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 5, 3, 5, 2, 3, 2 };
int N = 6;
int M = 3;
System.out.println(maxUniqueNum(arr, N, M));
}
}
Python3
# A python3 programme to find maximum # distinct elements in a subarray of size k # Function to find maximum unique # element in a subarray of size k def maxUniqueNum(a, N, M): maxUnique = 0 # search every subarray of size k and # find how many unique element present for i in range(N - M + 1): # create an empty set to store # the unique elements s = set() for j in range(M): # insert all elements # duplicate elements are not # stored in set s.add(a[i + j]) # update the maxUnique if(len(s) > maxUnique): maxUnique = len(s) return maxUnique # Driver Code if __name__ == '__main__': arr = [5, 3, 5, 2, 3, 2] M = 3 N = len(arr) print(maxUniqueNum(arr, N, M)) # This code is contributed by # Sanjit_Prasad
C#
// C# Program to find maximum number of
// Unique integers in Sub-Array
// of given size
using System;
using System.Collections.Generic;
class GFG
{
// Function to find maximum number of
// Unique integers in Sub-Array
// of given size
public static int maxUniqueNum(int []arr,
int N, int M)
{
int maxUnique = 0;
// Generate all subarrays of size M
for (int i = 0; i <= N - M; i++)
{
int currentUnique = 0;
Dictionary<int,int> map = new Dictionary<int,int>();
for (int k = i; k < i + M; k++)
{
// if the key is new to the map,
// push the key in map and increment
// count for unique number
if (!map.ContainsKey(arr[k]))
{
map.Remove(arr[i]);
map.Add(arr[i], 1);
currentUnique++;
continue;
}
}
if (currentUnique > maxUnique)
maxUnique = currentUnique;
}
return maxUnique;
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 5, 3, 5, 2, 3, 2 };
int N = 6;
int M = 3;
Console.WriteLine(maxUniqueNum(arr, N, M));
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript Program to find maximum number of
// Unique integers in Sub-Array
// of given size
// Function to find maximum number of
// Unique integers in Sub-Array
// of given size
function maxUniqueNum(arr,N,M)
{
let maxUnique = 0;
// Generate all subarrays of size M
for (let i = 0; i <= N - M; i++) {
let currentUnique = 0;
let map = new Map();
for (let k = i; k < i + M; k++) {
// if the key is new to the map,
// push the key in map and increment
// count for unique number
if (!map.has(arr[k])) {
map.set(arr[i], 1);
currentUnique++;
}
}
if (currentUnique > maxUnique)
maxUnique = currentUnique;
}
return maxUnique;
}
// Driver Code
let arr=[5, 3, 5, 2, 3, 2 ];
let N = 6;
let M = 3;
document.write(maxUniqueNum(arr, N, M));
// This code is contributed by unknown2108
</script>
Producción:
3
Complejidad de tiempo: O(M * N)
Espacio auxiliar: O(M)
Solución eficiente Una solución eficiente es utilizar la técnica de deslizamiento de ventanas . Mantenemos una sola tabla hash para almacenar elementos únicos de cada ventana.
1) Almacene los recuentos de los primeros M elementos en un mapa hash.
2) Atraviese desde (M+1)-ésimo elemento y para cada elemento, agréguelo al mapa hash y elimine el primer elemento de la ventana anterior.
A continuación se muestra la implementación del enfoque anterior:
C++
// An efficient Approach to count distinct elements in
// every window of size k
#include<bits/stdc++.h>
using namespace std;
//Function to find maximum unique element in
//a subarray of size k
int max_U_element(int a[],int N,int M)
{
//map to store the unique elements and their size
map<int,int> hash;
//Number of unique elements in an window
int dist_count=0;
int res=0; //Maximum unique element in a window
//store all elements till size k i.e.
//storing first window
for(int i=0;i<M;i++)
{
//found an unique element
if(hash.find(a[i])==hash.end())
{
hash.insert(make_pair(a[i],1));
dist_count++;
}
//an Duplicate element inserting
else
{
//Update the size of that element
hash[a[i]]++;
}
}
res=dist_count;
//Traverse till the end of array
for(int i=M;i<N;i++)
{
//Remove first element from map
if(hash[a[i-M]]==1)
{
//when element present only one time
// in window so delete this
hash.erase(a[i-M]);
dist_count--;
}
else
{
//when multiple time element has occurred
// in window so decrease size by one
hash[a[i-M]]--;
}
//Add new element to map
//If element is unique to map
//increment count
if(hash.find(a[i])==hash.end())
{
hash.insert(make_pair(a[i],1));
dist_count++;
}
//Duplicate element found
//update the size of that element
else
{
hash[a[i]]++;
}
//Update the res
res=max(res,dist_count);
}
return res;
}
//Driver code
int main()
{
int arr[] = {1, 2, 1, 3, 4, 2, 3};
int M=4,N=sizeof(arr)/sizeof(arr[0]);
cout<<max_U_element(arr,N,M)<<endl;
}
Java
// An efficient Java program to count distinct elements in
// every window of size k
import java.util.HashMap;
class maxUniqueNumWindow {
static int maxUniqueNum(int arr[], int M)
{
// Creates an empty hashMap hM
HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
// initialize distinct element count for
// current window
int dist_count = 0;
// Traverse the first window and store count
// of every element in hash map
for (int i = 0; i < M; i++) {
if (hM.get(arr[i]) == null) {
hM.put(arr[i], 1);
dist_count++;
}
else {
int count = hM.get(arr[i]);
hM.put(arr[i], count + 1);
}
}
int res = dist_count;
// Traverse through the remaining array
for (int i = M; i < arr.length; i++) {
// Remove first element of previous window
// If there was only one occurrence, then
// reduce distinct count.
if (hM.get(arr[i - M]) == 1) {
hM.remove(arr[i - M]);
dist_count--;
}
else // reduce count of the removed element
{
int count = hM.get(arr[i - M]);
hM.put(arr[i - M], count - 1);
}
// Add new element of current window
// If this element appears first time,
// increment distinct element count
if (hM.get(arr[i]) == null) {
hM.put(arr[i], 1);
dist_count++;
}
else // Increment distinct element count
{
int count = hM.get(arr[i]);
hM.put(arr[i], count + 1);
}
res = Math.max(res, dist_count);
}
return res;
}
// Driver method
public static void main(String arg[])
{
int arr[] = { 1, 2, 1, 3, 4, 2, 3 };
int M = 4;
System.out.println(maxUniqueNum(arr, M));
}
}
Python3
# An efficient Approach to count distinct elements in # every window of size k # Function to find maximum unique element in # a subarray of size k def max_U_element(a, N, M): # map to store the unique elements and their size hsh = dict() # Number of unique elements in an window dist_count = 0 res = 0 # Maximum unique element in a window # store all elements till size k i.e. # storing first window for i in range(M): # found an unique element if(arr[i] not in hsh.keys()): hsh[a[i]] = 1 dist_count += 1 # an Duplicate element inserting else: # Update the size of that element hsh[a[i]] += 1 res = dist_count # Traverse till the end of array for i in range(M, N): # Remove first element from map if(a[i - M] in hsh.keys() and hsh[a[i - M]] == 1): # when element present only one time # in window so delete this del hsh[a[i-M]] dist_count -= 1 else: # when multiple time element has occurred # in window so decrease size by one hsh[a[i - M]] -= 1 # Add new element to map # If element is unique to map # increment count if(a[i] not in hsh.keys()): hsh[a[i]] = 1 dist_count += 1 # Duplicate element found # update the size of that element else: hsh[a[i]] += 1 # Update the res res = max(res, dist_count) return res # Driver code arr = [1, 2, 1, 3, 4, 2, 3] M = 4 N = len(arr) print(max_U_element(arr, N, M)) # This code is contributed by mohit kumar
C#
// An efficient C# program to
// count distinct elements in
// every window of size k
using System;
using System.Collections.Generic;
class GFG
{
static int maxUniqueNum(int []arr, int M)
{
// Creates an empty hashMap hM
Dictionary<int,
int> hM = new Dictionary<int,
int>();
// initialize distinct element count
// for current window
int dist_count = 0;
// Traverse the first window and store
// count of every element in hash map
for (int i = 0; i < M; i++)
{
if (!hM.ContainsKey(arr[i]))
{
hM.Add(arr[i], 1);
dist_count++;
}
else
{
int count = hM[arr[i]];
hM[arr[i]] = count + 1;
}
}
int res = dist_count;
// Traverse through the remaining array
for (int i = M; i < arr.Length; i++)
{
// Remove first element of previous window
// If there was only one occurrence, then
// reduce distinct count.
if (hM[arr[i - M]] == 1)
{
hM.Remove(arr[i - M]);
dist_count--;
}
// reduce count of the removed element
else
{
int count = hM[arr[i - M]];
hM[arr[i - M]] = count - 1;
}
// Add new element of current window
// If this element appears first time,
// increment distinct element count
if (!hM.ContainsKey(arr[i]))
{
hM.Add(arr[i], 1);
dist_count++;
}
// Increment distinct element count
else
{
int count = hM[arr[i]];
hM[arr[i]] = count + 1;
}
res = Math.Max(res, dist_count);
}
return res;
}
// Driver Code
public static void Main(String []arg)
{
int []arr = { 1, 2, 1, 3, 4, 2, 3 };
int M = 4;
Console.WriteLine(maxUniqueNum(arr, M));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// An efficient JavaScript program to
// count distinct elements in
// every window of size k
function maxUniqueNum(arr,m)
{
// Creates an empty hashMap hM
let hM = new Map();
// initialize distinct element count for
// current window
let dist_count = 0;
// Traverse the first window and store count
// of every element in hash map
for (let i = 0; i < M; i++) {
if (hM.get(arr[i]) == null) {
hM.set(arr[i], 1);
dist_count++;
}
else {
let count = hM.get(arr[i]);
hM.set(arr[i], count + 1);
}
}
let res = dist_count;
// Traverse through the remaining array
for (let i = M; i < arr.length; i++) {
// Remove first element of previous window
// If there was only one occurrence, then
// reduce distinct count.
if (hM.get(arr[i - M]) == 1) {
hM.delete(arr[i - M]);
dist_count--;
}
else // reduce count of the removed element
{
let count = hM.get(arr[i - M]);
hM.set(arr[i - M], count - 1);
}
// Add new element of current window
// If this element appears first time,
// increment distinct element count
if (hM.get(arr[i]) == null) {
hM.set(arr[i], 1);
dist_count++;
}
else // Increment distinct element count
{
let count = hM.get(arr[i]);
hM.set(arr[i], count + 1);
}
res = Math.max(res, dist_count);
}
return res;
}
// Driver method
let arr=[1, 2, 1, 3, 4, 2, 3];
let M = 4;
document.write(maxUniqueNum(arr, M));
// This code is contributed by patel2127
</script>
Producción:
4
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(M)
Publicación traducida automáticamente
Artículo escrito por sjchatterjee_73 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA