Dado un arreglo arr[] que consta de N enteros y un entero positivo M , la tarea es encontrar la frecuencia máxima para cada subarreglo de longitud M ( 0 < M ≤ N ).
Ejemplos:
Entrada: arr[] = {1, 2, 3, 1, 2, 4, 1, 4, 4}, M = 4 Salida
: 2 2 1 2 2 3
Explicación:
Todos los subconjuntos de longitud M con la frecuencia máxima de cualquier elemento son:
- {1, 2, 3, 1}, la frecuencia máxima de un elemento es 2.
- {2, 3, 1, 2}, la frecuencia máxima de un elemento es 2.
- {3, 1, 2, 4}, La frecuencia máxima de un elemento es 1.
- {1, 2, 4, 1}, la frecuencia máxima de un elemento es 2.
- {2, 4, 1, 4}, la frecuencia máxima de un elemento es 2.
- {4, 1, 4, 4}, La frecuencia máxima de un elemento es 3.
Entrada: arr[] = {1, 1, 2, 2, 3, 5}, M = 4
Salida: 2 2 2ing
Enfoque: El problema dado puede resolverse encontrando las frecuencias para cada subarreglo de tamaño M que imprima la frecuencia máxima entre todas. Siga los pasos a continuación para resolver el problema dado:
- Inicialice un mapa desordenado , diga M para almacenar las frecuencias de los elementos del arreglo .
- Inicialice la variable, diga val como 0 para almacenar la frecuencia máxima de un elemento del subarreglo.
- Iterar sobre el rango [0, N] usando la variable i y realizar los siguientes pasos:
- Si el valor de (i – M) es mayor que igual a 0 , entonces disminuya el valor de A[i – M] del mapa M.
- Agregue el valor de arr[i] en el mapa M .
- Iterar sobre el mapa M y actualizar el valor de val como el máximo de val o x.segundo .
- Imprima el valor de val como el máximo para el subarreglo actual de tamaño M.
A continuación se muestra una implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the frequency of
// the most common element in each M
// length subarrays
void maxFrequencySubarrayUtil(
vector<int> A, int N, int M)
{
int i = 0;
// Stores frequency of array element
unordered_map<int, int> m;
// Stores the maximum frequency
int val = 0;
// Iterate for the first sub-array
// and store the maximum
for (; i < M; i++) {
m[A[i]]++;
val = max(val, m[A[i]]);
}
// Print the maximum frequency for
// the first subarray
cout << val << " ";
// Iterate over the range [M, N]
for (i = M; i < N; i++) {
// Subtract the A[i - M] and
// add the A[i] in the map
m[A[i - M]]--;
m[A[i]]++;
val = 0;
// Find the maximum frequency
for (auto x : m) {
val = max(val, x.second);
}
// Print the maximum frequency
// for the current subarray
cout << val << " ";
}
}
// Driver Code
int main()
{
vector<int> A = { 1, 1, 2, 2, 3, 5 };
int N = A.size();
int M = 4;
maxFrequencySubarrayUtil(A, N, M);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the frequency of
// the most common element in each M
// length subarrays
static void maxFrequencySubarrayUtil(int[] A, int N, int M) {
int i = 0;
// Stores frequency of array element
HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
// Stores the maximum frequency
int val = 0;
// Iterate for the first sub-array
// and store the maximum
for (; i < M; i++) {
if (m.containsKey(A[i])) {
m.put(A[i], m.get(A[i]) + 1);
} else {
m.put(A[i], 1);
}
val = Math.max(val, m.get(A[i]));
}
// Print the maximum frequency for
// the first subarray
System.out.print(val + " ");
// Iterate over the range [M, N]
for (i = M; i < N; i++) {
// Subtract the A[i - M] and
// add the A[i] in the map
if (m.containsKey(i - M)) {
m.put(i - M, m.get(i - M) - 1);
}
if (m.containsKey(A[i])) {
m.put(A[i], m.get(A[i]) + 1);
} else {
m.put(A[i], 1);
}
val = 0;
// Find the maximum frequency
for (Map.Entry<Integer, Integer> x : m.entrySet()) {
val = Math.max(val, x.getValue());
}
// Print the maximum frequency
// for the current subarray
System.out.print(val + " ");
}
}
// Driver Code
public static void main(String[] args) {
int[] A = { 1, 1, 2, 2, 3, 5 };
int N = A.length;
int M = 4;
maxFrequencySubarrayUtil(A, N, M);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program for the above approach
# Function to find the frequency of
# the most common element in each M
# length subarrays
def maxFrequencySubarrayUtil(A,N,M):
i = 0
# Stores frequency of array element
m = {}
# Stores the maximum frequency
val = 0
# Iterate for the first sub-array
# and store the maximum
while(i < M):
if A[i] in m:
m[A[i]] += 1
else:
m[A[i]] = 1
val = max(val, m[A[i]])
i += 1
# Print the maximum frequency for
# the first subarray
print(val,end = " ")
# Iterate over the range [M, N]
for i in range(M,N,1):
# Subtract the A[i - M] and
# add the A[i] in the map
if A[i - M] in m:
m[A[i - M]] -= 1
else:
m[A[i - M]] = 0
if A[i] in m:
m[A[i]] += 1
val = 0
# Find the maximum frequency
for key,value in m.items():
val = max(val, value)
# Print the maximum frequency
# for the current subarray
print(val,end=" ")
# Driver Code
if __name__ == '__main__':
A = [1, 1, 2, 2, 3, 5]
N = len(A)
M = 4
maxFrequencySubarrayUtil(A, N, M)
# This code is contributed by ipg2016107.
C#
using System;
using System.Collections.Generic;
public class GFG {
// Function to find the frequency of
// the most common element in each M
// length subarrays
static void maxFrequencySubarrayUtil(int[] A, int N,
int M)
{
int i = 0;
// Stores frequency of array element
Dictionary<int, int> m = new Dictionary<int, int>();
// Stores the maximum frequency
int val = 0;
// Iterate for the first sub-array
// and store the maximum
for (; i < M; i++) {
if (m.ContainsKey(A[i])) {
val = m[A[i]];
m.Remove(A[i]);
m.Add(A[i], val + 1);
}
else {
m.Add(A[i], 1);
}
val = Math.Max(val, m[A[i]]);
}
// Print the maximum frequency for
// the first subarray
Console.Write(val + " ");
// Iterate over the range [M, N]
for (i = M; i < N; i++) {
// Subtract the A[i - M] and
// add the A[i] in the map
if (m.ContainsKey(i - M)) {
val = i - M;
m.Remove(i - M);
m.Add(i - M, val - 1);
}
if (m.ContainsKey(A[i])) {
val = m[A[i]];
m.Remove(A[i]);
m.Add(A[i], val + 1);
}
else {
m.Add(A[i], 1);
}
val = Math.Max(val, m[A[i]]);
val = 0;
// Find the maximum frequency
foreach(KeyValuePair<int, int> x in m)
{
val = Math.Max(val, x.Value);
}
// Print the maximum frequency
// for the current subarray
Console.Write(val + " ");
}
}
// Driver Code
static public void Main()
{
int[] A = { 1, 1, 2, 2, 3, 5 };
int N = 6;
int M = 4;
maxFrequencySubarrayUtil(A, N, M);
}
}
// This code is contributed by maddler.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the frequency of
// the most common element in each M
// length subarrays
function maxFrequencySubarrayUtil(A, N, M)
{
// Stores frequency of array element
let m = new Map();
// Stores the maximum frequency
let val = 0;
// Iterate for the first sub-array
// and store the maximum
for (let i = 0; i < M; i++) {
if (m.has(A[i])) {
m.set(m.get(A[i]), m.get(A[i]) + 1);
}
else {
m.set(A[i], 1);
}
val = Math.max(val, m.get(A[i]));
}
// Print the maximum frequency for
// the first subarray
document.write(val + " ");
// Iterate over the range [M, N]
for (i = M; i < N; i++) {
// Subtract the A[i - M] and
// add the A[i] in the map
if (m.has(A[i - m]))
m.set(m.get(A[i - M]), m.get(A[i - M]) - 1);
if (m.has(A[i]))
m.set(m.get(A[i]), m.get(A[i]) + 1);
val = 0;
// Find the maximum frequency
for (let [key, value] of m) {
val = Math.max(val, value);
}
// Print the maximum frequency
// for the current subarray
document.write(val + " ");
}
}
// Driver Code
let A = [1, 1, 2, 2, 3, 5];
let N = A.length;
let M = 4;
maxFrequencySubarrayUtil(A, N, M);
// This code is contributed by Potta Lokesh
</script>
Producción:
2 2 2
Complejidad temporal: O(N*M)
Espacio auxiliar: O(M)