Consultas de rango para frecuencias de elementos de array

Dada una array de n enteros no negativos. La tarea es encontrar la frecuencia de un elemento particular en el rango arbitrario de array[]. El rango se proporciona como posiciones (no como índices basados ​​en 0) en la array. Puede haber múltiples consultas de un tipo determinado.

Ejemplos: 

Input  : arr[] = {2, 8, 6, 9, 8, 6, 8, 2, 11};
         left = 2, right = 8, element = 8
         left = 2, right = 5, element = 6      
Output : 3
         1
The element 8 appears 3 times in arr[left-1..right-1]
The element 6 appears 1 time in arr[left-1..right-1]

Enfoque ingenuo: es recorrer de izquierda a derecha y actualizar la variable de conteo cada vez que encontramos el elemento. 

A continuación se muestra el código del enfoque Naive: – 

// C++ program to find total count of an element
// in a range
#include<bits/stdc++.h>
using namespace std;
 
// Returns count of element in arr[left-1..right-1]
int findFrequency(int arr[], int n, int left,
                         int right, int element)
{
    int count = 0;
    for (int i=left-1; i<=right; ++i)
        if (arr[i] == element)
            ++count;
    return count;
}
 
// Driver Code
int main()
{
    int arr[] = {2, 8, 6, 9, 8, 6, 8, 2, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Print frequency of 2 from position 1 to 6
    cout << "Frequency of 2 from 1 to 6 = "
         << findFrequency(arr, n, 1, 6, 2) << endl;
 
    // Print frequency of 8 from position 4 to 9
    cout << "Frequency of 8 from 4 to 9 = "
         << findFrequency(arr, n, 4, 9, 8);
 
    return 0;
}

// JAVA Code to find total count of an element
// in a range
 
class GFG {
     
    // Returns count of element in arr[left-1..right-1]
    public static int findFrequency(int arr[], int n,
                                int left, int right,
                                      int element)
    {
        int count = 0;
        for (int i = left - 1; i < right; ++i)
            if (arr[i] == element)
                ++count;
        return count;
    }
     
    /* Driver program to test above function */
    public static void main(String[] args)
    {
        int arr[] = {2, 8, 6, 9, 8, 6, 8, 2, 11};
        int n = arr.length;
      
        // Print frequency of 2 from position 1 to 6
        System.out.println("Frequency of 2 from 1 to 6 = " +
             findFrequency(arr, n, 1, 6, 2));
      
        // Print frequency of 8 from position 4 to 9
        System.out.println("Frequency of 8 from 4 to 9 = " +
             findFrequency(arr, n, 4, 9, 8));
         
    }
  }
// This code is contributed by Arnav Kr. Mandal.

# Python program to find total 
# count of an element in a range
 
# Returns count of element
# in arr[left-1..right-1]
def findFrequency(arr, n, left, right, element):
 
    count = 0
    for i in range(left - 1, right):
        if (arr[i] == element):
            count += 1
    return count
 
 
# Driver Code
arr = [2, 8, 6, 9, 8, 6, 8, 2, 11]
n = len(arr)
 
# Print frequency of 2 from position 1 to 6
print("Frequency of 2 from 1 to 6 = ",
        findFrequency(arr, n, 1, 6, 2))
 
# Print frequency of 8 from position 4 to 9
print("Frequency of 8 from 4 to 9 = ",
        findFrequency(arr, n, 4, 9, 8))
         
     
# This code is contributed by Anant Agarwal.

// C# Code to find total count
// of an element in a range
using System;
 
class GFG {
     
    // Returns count of element
    // in arr[left-1..right-1]
    public static int findFrequency(int []arr, int n,
                                    int left, int right,
                                    int element)
    {
        int count = 0;
        for (int i = left - 1; i < right; ++i)
            if (arr[i] == element)
                ++count;
        return count;
    }
     
    // Driver Code
    public static void Main()
    {
        int []arr = {2, 8, 6, 9, 8, 6, 8, 2, 11};
        int n = arr.Length;
     
        // Print frequency of 2
        // from position 1 to 6
        Console.WriteLine("Frequency of 2 from 1 to 6 = " +
                            findFrequency(arr, n, 1, 6, 2));
     
        // Print frequency of 8
        // from position 4 to 9
        Console.Write("Frequency of 8 from 4 to 9 = " +
                       findFrequency(arr, n, 4, 9, 8));
         
    }
}
 
// This code is contributed by Nitin Mittal.

<?php
// PHP program to find total count of
// an element in a range
 
// Returns count of element in
// arr[left-1..right-1]
function findFrequency(&$arr, $n, $left,
                        $right, $element)
{
    $count = 0;
    for ($i = $left - 1; $i <= $right; ++$i)
        if ($arr[$i] == $element)
            ++$count;
    return $count;
}
 
// Driver Code
$arr = array(2, 8, 6, 9, 8, 6, 8, 2, 11);
$n = sizeof($arr);
 
// Print frequency of 2 from position 1 to 6
echo "Frequency of 2 from 1 to 6 = ".
      findFrequency($arr, $n, 1, 6, 2) ."\n";
 
// Print frequency of 8 from position 4 to 9
echo "Frequency of 8 from 4 to 9 = ".
      findFrequency($arr, $n, 4, 9, 8);
 
// This code is contributed by ita_c
?>

<script>
 
// Javascript Code to find total count of an element
// in a range
     
    // Returns count of element in arr[left-1..right-1]
    function findFrequency(arr,n,left,right,element)
    {
        let count = 0;
        for (let i = left - 1; i < right; ++i)
            if (arr[i] == element)
                ++count;
        return count;
    }
     
    /* Driver program to test above function */
    let arr=[2, 8, 6, 9, 8, 6, 8, 2, 11];
    let n = arr.length;
     
    // Print frequency of 2 from position 1 to 6
    document.write("Frequency of 2 from 1 to 6 = " +
             findFrequency(arr, n, 1, 6, 2)+"<br>");
     
    // Print frequency of 8 from position 4 to 9
    document.write("Frequency of 8 from 4 to 9 = " +
             findFrequency(arr, n, 4, 9, 8));
     
    // This code is contributed by rag2127
     
</script>

Frequency of 2 from 1 to 6 = 1
Frequency of 8 from 4 to 9 = 2

La complejidad temporal de este enfoque es O(derecha – izquierda + 1) u O(n) 
Espacio auxiliar : O(1)

Un enfoque eficiente es usar hashing. En C++, podemos usar unordered_map

• Al principio, almacenaremos la posición en el mapa [] de cada elemento distinto como un vector como ese 

  int arr[] = {2, 8, 6, 9, 8, 6, 8, 2, 11};
  map[2] = {1, 8}
  map[8] = {2, 5, 7}
  map[6] = {3, 6} 
  ans so on...

• Como podemos ver que los elementos en map[] ya están ordenados (porque insertamos elementos de izquierda a derecha), la respuesta se reduce a encontrar el recuento total en ese hash map[] usando un método de búsqueda binaria. 
   
• En C++ podemos usar lower_bound que devolverá un iterador que apunta al primer elemento en el rango [first, last] que tiene un valor no menor que ‘left’. y upper_bound devuelve un iterador que apunta al primer elemento en el rango [primero, último] que tiene un valor mayor que ‘derecho’. 
   
• Después de eso, solo tenemos que restar el resultado de upper_bound() y lower_bound() para obtener la respuesta final. Por ejemplo, supongamos que queremos encontrar el recuento total de 8 en el rango de [1 a 6], entonces la función map[8] de lower_bound() devolverá el resultado 0 (apuntando a 2) y upper_bound() lo hará. devuelve 2 (apuntando a 7), por lo que debemos restar ambos resultados como 2 – 0 = 2. 
   

A continuación se muestra el código del enfoque anterior. 

// C++ program to find total count of an element
#include<bits/stdc++.h>
using namespace std;
 
unordered_map< int, vector<int> > store;
 
// Returns frequency of element in arr[left-1..right-1]
int findFrequency(int arr[], int n, int left,
                      int right, int element)
{
    // Find the position of first occurrence of element
    int a = lower_bound(store[element].begin(),
                        store[element].end(),
                        left)
            - store[element].begin();
 
    // Find the position of last occurrence of element
    int b = upper_bound(store[element].begin(),
                        store[element].end(),
                        right)
            - store[element].begin();
 
    return b-a;
}
 
// Driver code
int main()
{
    int arr[] = {2, 8, 6, 9, 8, 6, 8, 2, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Storing the indexes of an element in the map
    for (int i=0; i<n; ++i)
        store[arr[i]].push_back(i+1); //starting index from 1
 
    // Print frequency of 2 from position 1 to 6
    cout << "Frequency of 2 from 1 to 6 = "
         << findFrequency(arr, n, 1, 6, 2) <<endl;
 
    // Print frequency of 8 from position 4 to 9
    cout << "Frequency of 8 from 4 to 9 = "
         << findFrequency(arr, n, 4, 9, 8);
 
    return 0;
}

# Python3 program to find total count of an element
from collections import defaultdict as dict
from bisect import bisect_left as lower_bound
from bisect import bisect_right as upper_bound
 
store = dict(list)
 
# Returns frequency of element
# in arr[left-1..right-1]
def findFrequency(arr, n, left, right, element):
     
    # Find the position of
    # first occurrence of element
    a = lower_bound(store[element], left)
 
    # Find the position of
    # last occurrence of element
    b = upper_bound(store[element], right)
 
    return b - a
 
# Driver code
arr = [2, 8, 6, 9, 8, 6, 8, 2, 11]
n = len(arr)
 
# Storing the indexes of
# an element in the map
for i in range(n):
    store[arr[i]].append(i + 1)
 
# Print frequency of 2 from position 1 to 6
print("Frequency of 2 from 1 to 6 = ",
       findFrequency(arr, n, 1, 6, 2))
 
# Print frequency of 8 from position 4 to 9
print("Frequency of 8 from 4 to 9 = ",
       findFrequency(arr, n, 4, 9, 8))
 
# This code is contributed by Mohit Kumar

Frequency of 2 from 1 to 6 = 1
Frequency of 8 from 4 to 9 = 2

Este enfoque será beneficioso si tenemos una gran cantidad de consultas de un rango arbitrario que preguntan la frecuencia total de un elemento en particular.
Complejidad de tiempo: O (log N) para consulta única.

Este artículo es una contribución de Shubham Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.