Frecuencias máximas en cada subarreglo de longitud M

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. {1, 2, 3, 1}, la frecuencia máxima de un elemento es 2.
  2. {2, 3, 1, 2}, la frecuencia máxima de un elemento es 2.
  3. {3, 1, 2, 4}, La frecuencia máxima de un elemento es 1.
  4. {1, 2, 4, 1}, la frecuencia máxima de un elemento es 2.
  5. {2, 4, 1, 4}, la frecuencia máxima de un elemento es 2.
  6. {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)

Publicación traducida automáticamente

Artículo escrito por offbeat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *