Dada una array de tamaño n y un entero k, devuelve el recuento de números distintos en todas las ventanas de tamaño k.
Ejemplo:
C++
// Simple C++ program to count distinct
// elements in every window of size k
#include <bits/stdc++.h>
using namespace std;
// Counts distinct elements in window of size k
int countWindowDistinct(int win[], int k)
{
int dist_count = 0;
// Traverse the window
for (int i = 0; i < k; i++) {
// Check if element arr[i] exists in arr[0..i-1]
int j;
for (j = 0; j < i; j++)
if (win[i] == win[j])
break;
if (j == i)
dist_count++;
}
return dist_count;
}
// Counts distinct elements in all windows of size k
void countDistinct(int arr[], int n, int k)
{
// Traverse through every window
for (int i = 0; i <= n - k; i++)
cout << countWindowDistinct(arr + i, k) << endl;
}
// Driver program
int main()
{
int arr[] = { 1, 2, 1, 3, 4, 2, 3 }, k = 4;
int n = sizeof(arr) / sizeof(arr[0]);
countDistinct(arr, n, k);
return 0;
}
Java
// Simple Java program to count distinct elements in every
// window of size k
import java.util.Arrays;
class Test {
// Counts distinct elements in window of size k
static int countWindowDistinct(int win[], int k)
{
int dist_count = 0;
// Traverse the window
for (int i = 0; i < k; i++) {
// Check if element arr[i] exists in arr[0..i-1]
int j;
for (j = 0; j < i; j++)
if (win[i] == win[j])
break;
if (j == i)
dist_count++;
}
return dist_count;
}
// Counts distinct elements in all windows of size k
static void countDistinct(int arr[], int n, int k)
{
// Traverse through every window
for (int i = 0; i <= n - k; i++)
System.out.println(countWindowDistinct(Arrays.copyOfRange(arr, i, arr.length), k));
}
// Driver method
public static void main(String args[])
{
int arr[] = { 1, 2, 1, 3, 4, 2, 3 }, k = 4;
countDistinct(arr, arr.length, k);
}
}
Python3
# Simple Python3 program to count distinct # elements in every window of size k import math as mt # Counts distinct elements in window # of size k def countWindowDistinct(win, k): dist_count = 0 # Traverse the window for i in range(k): # Check if element arr[i] exists # in arr[0..i-1] j = 0 while j < i: if (win[i] == win[j]): break else: j += 1 if (j == i): dist_count += 1 return dist_count # Counts distinct elements in all # windows of size k def countDistinct(arr, n, k): # Traverse through every window for i in range(n - k + 1): print(countWindowDistinct(arr[i:k + i], k)) # Driver Code arr = [1, 2, 1, 3, 4, 2, 3] k = 4 n = len(arr) countDistinct(arr, n, k) # This code is contributed by # Mohit kumar 29
C#
// Simple C# program to count distinct
// elements in every window of size k
using System;
using System.Collections.Generic;
class GFG {
// Counts distinct elements in
// window of size k
static int countWindowDistinct(int[] win,
int k)
{
int dist_count = 0;
// Traverse the window
for (int i = 0; i < k; i++) {
// Check if element arr[i]
// exists in arr[0..i-1]
int j;
for (j = 0; j < i; j++)
if (win[i] == win[j])
break;
if (j == i)
dist_count++;
}
return dist_count;
}
// Counts distinct elements in
// all windows of size k
static void countDistinct(int[] arr,
int n, int k)
{
// Traverse through every window
for (int i = 0; i <= n - k; i++) {
int[] newArr = new int[k];
Array.Copy(arr, i, newArr, 0, k);
Console.WriteLine(countWindowDistinct(newArr, k));
}
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 1, 2, 1, 3, 4, 2, 3 };
int k = 4;
countDistinct(arr, arr.Length, k);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to count distinct elements in every
// window of size k
// Counts distinct elements in window of size k
function countWindowDistinct(win, k)
{
let dist_count = 0;
// Traverse the window
for (let i = 0; i < k; i++) {
// Check if element arr[i] exists in arr[0..i-1]
let j;
for (j = 0; j < i; j++)
if (win[i] == win[j])
break;
if (j == i)
dist_count++;
}
return dist_count;
}
// Counts distinct elements in all windows of size k
function countDistinct(arr, n, k)
{
// Traverse through every window
for (let i = 0; i <= n - k; i++)
document.write(countWindowDistinct(arr.slice(i, arr.length), k) + "<br/>");
}
// Driver program
let arr = [ 1, 2, 1, 3, 4, 2, 3 ], k = 4;
countDistinct(arr, arr.length, k);
// This code is contributed by target_2.
</script>
C++
// An efficient C++ program to
// count distinct elements in
// every window of size k
#include <iostream>
#include <unordered_map>
using namespace std;
void countDistinct(int arr[], int k, int n)
{
// Creates an empty hashmap hm
unordered_map<int, int> hm;
// 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 < k; i++) {
if (hm[arr[i]] == 0) {
dist_count++;
}
hm[arr[i]] += 1;
}
// Print count of first window
cout << dist_count << endl;
// Traverse through the remaining array
for (int i = k; i < n; i++) {
// Remove first element of previous window
// If there was only one occurrence, then reduce distinct count.
if (hm[arr[i - k]] == 1) {
dist_count--;
}
// reduce count of the removed element
hm[arr[i - k]] -= 1;
// Add new element of current window
// If this element appears first time,
// increment distinct element count
if (hm[arr[i]] == 0) {
dist_count++;
}
hm[arr[i]] += 1;
// Print count of current window
cout << dist_count << endl;
}
}
int main()
{
int arr[] = { 1, 2, 1, 3, 4, 2, 3 };
int size = sizeof(arr) / sizeof(arr[0]);
int k = 4;
countDistinct(arr, k, size);
return 0;
}
// This solution is contributed by Aditya Goel
Java
// An efficient Java program to count distinct elements in
// every window of size k
import java.util.HashMap;
class CountDistinctWindow {
static void countDistinct(int arr[], int k)
{
// Creates an empty hashMap hM
HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
// Traverse the first window and store count
// of every element in hash map
for (int i = 0; i < k; i++)
hM.put(arr[i], hM.getOrDefault(arr[i], 0) + 1);
// Print count of first window
System.out.println(hM.size());
// Traverse through the remaining array
for (int i = k; i < arr.length; i++) {
// Remove first element of previous window
// If there was only one occurrence
if (hM.get(arr[i - k]) == 1) {
hM.remove(arr[i - k]);
}
else // reduce count of the removed element
hM.put(arr[i - k], hM.get(arr[i - k]) - 1);
// Add new element of current window
// If this element appears first time,
// set its count as 1,
hM.put(arr[i], hM.getOrDefault(arr[i], 0) + 1);
// Print count of current window
System.out.println(hM.size());
}
}
// Driver method
public static void main(String arg[])
{
int arr[] = { 1, 2, 1, 3, 4, 2, 3 };
int k = 4;
countDistinct(arr, k);
}
}
Python3
# An efficient Python program to # count distinct elements in # every window of size k from collections import defaultdict def countDistinct(arr, k, n): # Creates an empty hashmap hm mp = defaultdict(lambda:0) # initialize distinct element # count for current window dist_count = 0 # Traverse the first window and store count # of every element in hash map for i in range(k): if mp[arr[i]] == 0: dist_count += 1 mp[arr[i]] += 1 # Print count of first window print(dist_count) # Traverse through the remaining array for i in range(k, n): # Remove first element of previous window # If there was only one occurrence, # then reduce distinct count. if mp[arr[i - k]] == 1: dist_count -= 1 mp[arr[i - k]] -= 1 # Add new element of current window # If this element appears first time, # increment distinct element count if mp[arr[i]] == 0: dist_count += 1 mp[arr[i]] += 1 # Print count of current window print(dist_count) arr = [1, 2, 1, 3, 4, 2, 3] n = len(arr) k = 4 countDistinct(arr, k, n) # This code is contributed by Shrikant13
C#
// An efficient C# program to count
// distinct elements in every window of size k
using System;
using System.Collections.Generic;
public class CountDistinctWindow {
static void countDistinct(int[] arr, int k)
{
// 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 < k; i++) {
if (!hM.ContainsKey(arr[i])) {
hM.Add(arr[i], 1);
dist_count++;
}
else {
int count = hM[arr[i]];
hM.Remove(arr[i]);
hM.Add(arr[i], count + 1);
}
}
// Print count of first window
Console.WriteLine(dist_count);
// Traverse through the remaining array
for (int i = k; i < arr.Length; i++) {
// Remove first element of previous window
// If there was only one occurrence, then
// reduce distinct count.
if (hM[arr[i - k]] == 1) {
hM.Remove(arr[i - k]);
dist_count--;
}
else // reduce count of the removed element
{
int count = hM[arr[i - k]];
hM.Remove(arr[i - k]);
hM.Add(arr[i - k], 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++;
}
else // Increment distinct element count
{
int count = hM[arr[i]];
hM.Remove(arr[i]);
hM.Add(arr[i], count + 1);
}
// Print count of current window
Console.WriteLine(dist_count);
}
}
// Driver method
public static void Main(String[] arg)
{
int[] arr = { 1, 2, 1, 3, 4, 2, 3 };
int k = 4;
countDistinct(arr, k);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript program to count distinct elements in
// every window of size k
function countDistinct(arr, k)
{
// Creates an empty hashMap hM
let hM = new Map();
// Traverse the first window and store count
// of every element in hash map
for (let i = 0; i < k; i++)
{
if(hM.has(arr[i]))
hM.set(arr[i], hM.get(arr[i])+1)
else
hM.set(arr[i], 1);
}
// Print count of first window
document.write(hM.size + "<br/>");
// Traverse through the remaining array
for (let i = k; i < arr.length; i++) {
// Remove first element of previous window
// If there was only one occurrence
if (hM.get(arr[i - k]) == 1) {
hM.delete(arr[i - k]);
}
else // reduce count of the removed element
hM.set(arr[i - k], hM.get(arr[i - k]) - 1);
// Add new element of current window
// If this element appears first time,
// set its count as 1,
if(hM.has(arr[i]))
hM.set(arr[i], hM.get(arr[i])+1)
else
hM.set(arr[i], 1);
// Print count of current window
document.write(hM.size + "<br/>");
}
}
// Driver code
let arr = [ 1, 2, 1, 3, 4, 2, 3 ];
let size = arr.length;
let k = 4;
countDistinct(arr, k, size);
// This code is contributed by splevel62.
</script>
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