Recuento de subarreglos con X como elemento más frecuente, para cada valor de X de 1 a N

Dada una array arr[] de tamaño N, ( donde 0<A[i]<=N , para todos los 0<=i<N ), la tarea es calcular para cada número X de 1 a N , el número de subarreglos donde X es el elemento más frecuente. En subarreglos, donde más de un elemento tiene la frecuencia máxima, el elemento más pequeño debe ser considerado como el más frecuente.

Ejemplos:

Entrada: arr[]={2, 1, 2, 3}, N=4
Salida:
4 5 1 0
Explicación:

1. Para X=1, los subarreglos donde X es el elemento más frecuente son {2, 1}, {1}, {1, 2}, {1, 2, 3}
2. Para X=2, los subarreglos donde X es el elemento más frecuente son {2}, {2, 1, 2}, {2, 1, 2, 3}, {2}, {2, 3}
3. Para X=3, el subarreglo donde X es el elemento más frecuente, es {3}
4. Para X=4, no hay subarreglos que contengan 4.

Entrada: arr[]={3, 1, 5, 1, 3}, N=5
Salida:
12 0 2 0 1

Enfoque: el enfoque consiste en realizar un seguimiento del elemento más frecuente en cada subarreglo mediante dos bucles y mantenerlos almacenados en un arreglo separado. Siga los pasos a continuación para resolver el problema:

1. Inicialice una array ans de tamaño N a 0 para almacenar las respuestas finales.
2. Iterar de 0 a N-1 , y para cada índice actual i , hacer lo siguiente:
   1. Inicialice un conteo de array de frecuencia de tamaño N a 0 , para almacenar las frecuencias actuales de cada elemento de 1 a N.
   2. Inicialice una variable best a 0 , para almacenar el elemento más frecuente en el subarreglo actual.
   3. Iterar de i a N-1 , y para cada índice actual j , hacer lo siguiente:
      1. Incremente el conteo del elemento actual, es decir, conteo[arr[j]-1]=conteo[arr[j]-1]+1
      2. Compruebe si la frecuencia del elemento actual, es decir, arr[j], es mayor que la frecuencia del mejor.
      3. Compruebe si la frecuencia del elemento actual, es decir, arr[j], es igual a la frecuencia del mejor y el elemento actual es menor que el mejor .
      4. Si alguno de ellos es verdadero, actualice best al elemento actual, es decir, best=arr[j]
      5. Incremente el mejor índice de la array ans , es decir ans[best-1]=ans[best-1]+1 .
3. Imprime la array ans .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the number of subarrays where
// X(1<=X<=N) is the most frequent element
int mostFrequent(int arr[], int N)
{
    // array to store the final answers
    int ans[N] = { 0 };
 
    for (int i = 0; i < N; i++) {
 
        // Array to store current frequencies
        int count[N];
 
        // Initialise count
        memset(count, 0, sizeof(count));
 
        // Variable to store the
        // current most frequent element
        int best = 0;
        for (int j = i; j < N; j++) {
 
            // Update frequency array
            count[arr[j] - 1]++;
            if (count[arr[j] - 1] > count[best - 1]
                || (count[arr[j] - 1] == count[best - 1]
                    && arr[j] < best)) {
                best = arr[j];
            }
 
            // Update answer
            ans[best - 1]++;
        }
    }
 
    // Print answer
    for (int i = 0; i < N; i++)
        cout << ans[i] << " ";
}
// Driver code
int main()
{
    // Input
    int arr[] = { 2, 1, 2, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    mostFrequent(arr, N);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG {
 
    // Function to calculate the number of subarrays where
    // X(1<=X<=N) is the most frequent element
    public static void mostFrequent(int[] arr, int N)
    {
        // array to store the final answers
        int[] ans = new int[N];
 
        for (int i = 0; i < N; i++) {
 
            // Array to store current frequencies
            int[] count = new int[N];
 
            // Variable to store the
            // current most frequent element
            int best = 1;
            for (int j = i; j < N; j++) {
 
                // Update frequency array
                count[arr[j] - 1]++;
                if (best > 0) {
                    if ((count[arr[j] - 1]
                         > count[best - 1])
                        || (count[arr[j] - 1]
                                == count[best - 1]
                            && arr[j] < best)) {
                        best = arr[j];
                    }
 
                    // Update answer
                    ans[best - 1]++;
                }
            }
        }
 
        // Print answer
        for (int i = 0; i < N; i++)
        System.out.print(ans[i] + " ");
    }
 
    // Driver Code
    public static void main(String[] args)
    {
       
     // Input
        int[] arr = { 2, 1, 2, 3 };
        int N = arr.length;
 
        // Function call
        mostFrequent(arr, N);
    }
}
 
// This code is contributed by sanjoy_62.

# Python program for the above approach
 
# Function to calculate the number of subarrays where
# X(1<=X<=N) is the most frequent element
def mostFrequent(arr, N):
    # array to store the final answers
    ans = [0]*N
 
    for i in range(N):
        # Array to store current frequencies
        count = [0]*N
 
        # Initialise count
        # memset(count, 0, sizeof(count))
 
        # Variable to store the
        # current most frequent element
        best = 0
        for j in range(i,N):
            # Update frequency array
            count[arr[j] - 1]+=1
            if (count[arr[j] - 1] > count[best - 1]
                or (count[arr[j] - 1] == count[best - 1]
                    and arr[j] < best)):
                best = arr[j]
 
            # Update answer
            ans[best - 1] += 1
 
    # Print answer
    print(*ans)
     
# Driver code
if __name__ == '__main__':
    # Input
    arr= [2, 1, 2, 3]
    N = len(arr)
 
    # Function call
    mostFrequent(arr, N)
 
# This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
class GFG {
 
    // Function to calculate the number of subarrays where
    // X(1<=X<=N) is the most frequent element
    public static void mostFrequent(int[] arr, int N)
    {
        // array to store the final answers
        int[] ans = new int[N];
 
        for (int i = 0; i < N; i++) {
 
            // Array to store current frequencies
            int[] count = new int[N];
 
            // Variable to store the
            // current most frequent element
            int best = 1;
            for (int j = i; j < N; j++) {
 
                // Update frequency array
                count[arr[j] - 1]++;
                if (best > 0) {
                    if ((count[arr[j] - 1]
                         > count[best - 1])
                        || (count[arr[j] - 1]
                                == count[best - 1]
                            && arr[j] < best)) {
                        best = arr[j];
                    }
 
                    // Update answer
                    ans[best - 1]++;
                }
            }
        }
 
        // Print answer
        for (int i = 0; i < N; i++)
            Console.Write(ans[i] + " ");
    }
   
    // Driver code
    public static void Main()
    {
       
        // Input
        int[] arr = { 2, 1, 2, 3 };
        int N = arr.Length;
 
        // Function call
        mostFrequent(arr, N);
    }
}
 
// This code is contributed by subham348.

<script>
// Javascript program for the above approach
 
// Function to calculate the number of subarrays where
// X(1<=X<=N) is the most frequent element
function mostFrequent(arr, N) {
    // array to store the final answers
    let ans = new Array(N).fill(0)
 
    for (let i = 0; i < N; i++) {
 
        // Array to store current frequencies
        let count = new Array(N);
 
        // Initialise count
        count.fill(0)
 
        // Variable to store the
        // current most frequent element
        let best = 1;
        for (let j = i; j < N; j++) {
 
            // Update frequency array
            count[arr[j] - 1]++;
            if (count[arr[j] - 1] > count[best - 1]
                || (count[arr[j] - 1] == count[best - 1]
                    && arr[j] < best)) {
                best = arr[j];
            }
 
            // Update answer
            ans[best - 1]++;
        }
    }
 
    // Print answer
    console.log(ans)
    for (let i = 0; i < N; i++)
        document.write(ans[i] + " ");
}
 
 
// Driver code
// Input
let arr = [2, 1, 2, 3];
let N = arr.length
 
// Function call
mostFrequent(arr, N);
</script>

4 5 1 0

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)