Encuentra la frecuencia de un número en una array

Dada una array, a[] y un elemento x, encuentre un número de ocurrencias de x en a[].

Ejemplos: 

Input  : a[] = {0, 5, 5, 5, 4}
           x = 5
Output : 3

Input  : a[] = {1, 2, 3}
          x = 4
Output : 0

Si la array no está ordenada

La idea es simple, inicializamos count como 0. Atravesamos la array de forma lineal. Por cada elemento que coincida con x, incrementamos la cuenta. Finalmente, devolvemos la cuenta. 

A continuación se muestra la implementación del enfoque.

// CPP program to count occurrences of an
// element in an unsorted array
#include<iostream>
using namespace std;
 
int frequency(int a[], int n, int x)
{
    int count = 0;
    for (int i=0; i < n; i++)
       if (a[i] == x)
          count++;
    return count;
}
 
// Driver program
int main() {
    int a[] = {0, 5, 5, 5, 4};
    int x = 5;
    int n = sizeof(a)/sizeof(a[0]);
    cout << frequency(a, n, x);
    return 0;
}

// Java program to count
// occurrences of an
// element in an unsorted
// array
 
import java.io.*;
 
class GFG {
     
    static int frequency(int a[],
    int n, int x)
    {
        int count = 0;
        for (int i=0; i < n; i++)
        if (a[i] == x)
            count++;
        return count;
    }
     
    // Driver program
    public static void main (String[]
    args) {
         
        int a[] = {0, 5, 5, 5, 4};
        int x = 5;
        int n = a.length;
         
        System.out.println(frequency(a, n, x));
    }
}
 
// This code is contributed
// by Ansu Kumari

# Python program to count
# occurrences of an
# element in an unsorted
# array
def frequency(a, x):
    count = 0
     
    for i in a:
        if i == x: count += 1
    return count
 
# Driver program
a = [0, 5, 5, 5, 4]
x = 5
print(frequency(a, x))
 
# This code is contributed by Ansu Kumari

// C# program to count
// occurrences of an
// element in an unsorted
// array
using System;
 
class GFG {
     
    static int frequency(int []a,
    int n, int x)
    {
        int count = 0;
        for (int i=0; i < n; i++)
        if (a[i] == x)
            count++;
        return count;
    }
     
    // Driver program
    static public void Main (){
     
         
        int []a = {0, 5, 5, 5, 4};
        int x = 5;
        int n = a.Length;
         
        Console.Write(frequency(a, n, x));
    }
}
 
// This code is contributed
// by Anuj_67

<?php
// PHP program to count occurrences of an
// element in an unsorted array
 
function frequency($a, $n, $x)
{
    $count = 0;
    for ($i = 0; $i < $n; $i++)
    if ($a[$i] == $x)
        $count++;
    return $count;
}
 
    // Driver Code
    $a = array (0, 5, 5, 5, 4);
    $x = 5;
    $n = sizeof($a);
    echo frequency($a, $n, $x);
 
// This code is contributed by ajit
?>

<script>
    // C# program to count occurrences of an element in an unsorted array
     
    function frequency(a, n, x)
    {
        let count = 0;
        for (let i=0; i < n; i++)
        if (a[i] == x)
            count++;
        return count;
    }
     
    let a = [0, 5, 5, 5, 4];
    let x = 5;
    let n = a.length;
 
    document.write(frequency(a, n, x));
                              
</script>

3

Tiempo Complejidad : O(n) 
Espacio Auxiliar : O(1)

Si la array está ordenada

Podemos aplicar métodos tanto para ordenados como para no ordenados. Pero para una array ordenada, podemos optimizarla para que funcione en el tiempo O (Log n) usando Binary Search . Consulte el artículo a continuación para obtener más detalles. Cuente el número de ocurrencias (o frecuencia) en una array ordenada .

Si hay varias consultas en una sola array

Podemos usar hashing para almacenar frecuencias de todos los elementos. Entonces podemos responder todas las consultas en tiempo O (1). Consulte Frecuencia de cada elemento en una array no ordenada para obtener más información. 

Implementación:

// CPP program to answer queries for frequencies
// in O(1) time.
#include <bits/stdc++.h>
using namespace std;
  
unordered_map<int, int> hm;
 
void countFreq(int a[], int n)
{
    // Insert elements and their
    // frequencies in hash map.
    for (int i=0; i<n; i++)
        hm[a[i]]++;
}
 
// Return frequency of x (Assumes that
// countFreq() is called before)
int query(int x)
{
    return hm[x];
}
  
// Driver program
int main()
{
    int a[] = {1, 3, 2, 4, 2, 1};
    int n = sizeof(a)/sizeof(a[0]);
    countFreq(a, n);
    cout << query(2) << endl;
    cout << query(3) << endl;
    cout << query(5) << endl;
    return 0;
}

// Java program to answer
// queries for frequencies
// in O(1) time.
 
import java.io.*;
import java.util.*;
 
class GFG {
     
   static HashMap <Integer, Integer> hm = new HashMap<Integer, Integer>();
 
   static void countFreq(int a[], int n)
   {
        // Insert elements and their
        // frequencies in hash map.
        for (int i=0; i<n; i++)
            if (hm.containsKey(a[i]) )
                hm.put(a[i], hm.get(a[i]) + 1);
            else hm.put(a[i] , 1);
    }
     
    // Return frequency of x (Assumes that
    // countFreq() is called before)
    static int query(int x)
    {
        if (hm.containsKey(x))
            return hm.get(x);
        return 0;
    }
     
    // Driver program
    public static void main (String[] args) {
        int a[] = {1, 3, 2, 4, 2, 1};
        int n = a.length;
        countFreq(a, n);
        System.out.println(query(2));
        System.out.println(query(3));
        System.out.println(query(5));
    }
    }
 
// This code is contributed by Ansu Kumari

# Python program to
# answer queries for
# frequencies
# in O(1) time.
 
hm = {}
 
def countFreq(a):
    global hm
     
    # Insert elements and their
    # frequencies in hash map.
     
    for i in a:
        if i in hm: hm[i] += 1
        else: hm[i] = 1
 
# Return frequency
# of x (Assumes that
# countFreq() is
# called before)
def query(x):
    if x in hm:
        return hm[x]
    return 0
 
# Driver program
a = [1, 3, 2, 4, 2, 1]
countFreq(a)
print(query(2))
print(query(3))
print(query(5))
 
# This code is contributed
# by Ansu Kumari

// C# program to answer
// queries for frequencies
// in O(1) time.
using System;
using System.Collections.Generic;
class GFG
{
     
static Dictionary <int, int> hm = new Dictionary<int, int>();
 
static void countFreq(int []a, int n)
{
    // Insert elements and their
    // frequencies in hash map.
    for (int i = 0; i < n; i++)
        if (hm.ContainsKey(a[i]) )
            hm[a[i]] = hm[a[i]] + 1;
        else hm.Add(a[i], 1);
}
     
// Return frequency of x (Assumes that
// countFreq() is called before)
static int query(int x)
{
    if (hm.ContainsKey(x))
        return hm[x];
    return 0;
}
     
// Driver code
public static void Main(String[] args)
{
    int []a = {1, 3, 2, 4, 2, 1};
    int n = a.Length;
    countFreq(a, n);
    Console.WriteLine(query(2));
    Console.WriteLine(query(3));
    Console.WriteLine(query(5));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// JavaScript program to answer
// queries for frequencies
// in O(1) time.
  
var hm = new Map();
 
function countFreq(a, n)
{
    // Insert elements and their
    // frequencies in hash map.
    for (var i=0; i<n; i++)
    {
        if(hm.has(a[i]))
        {
            hm.set(a[i], hm.get(a[i])+1);
        }
        else
        {
            hm.set(a[i], 1);
        }
    }
}
 
// Return frequency of x (Assumes that
// countFreq() is called before)
function query(x)
{
    if(hm.has(x))
    {
        return hm.get(x);
    }
    return 0;
}
  
// Driver program
var a = [1, 3, 2, 4, 2, 1];
var n = a.length;
countFreq(a, n);
document.write( query(2) + "<br>");
document.write( query(3) + "<br>");
document.write( query(5) + "<br>");
 
</script>

2
1
0

Este artículo es una contribución de Sangita Dey . 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.