Diferencia entre las frecuencias más altas y más bajas en una array

Dada una array, encuentre la diferencia entre la ocurrencia más alta y la ocurrencia mínima de cualquier número en una array

Ejemplos: 

Input  : arr[] = [7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5]
Output : 2
Lowest occurring element (5) occurs once.
Highest occurring element (1 or 7) occurs 3 times

Input  : arr[] = [1, 1, 1, 3, 3, 3]
Output : 0

Una solución simple es usar dos bucles para contar la frecuencia de cada elemento y realizar un seguimiento de las frecuencias máximas y mínimas.
Una mejor solución es ordenar la array en O (n log n) y verificar la ocurrencia de elementos consecutivos y comparar su conteo respectivamente. 

Implementación:

// CPP code to find the difference between highest
// and least frequencies
#include <bits/stdc++.h>
using namespace std;
 
int findDiff(int arr[], int n)
{
    // sort the array
    sort(arr, arr + n);
 
    int count = 0, max_count = 0, min_count = n;
    for (int i = 0; i < (n - 1); i++) {
 
        // checking consecutive elements
        if (arr[i] == arr[i + 1]) {
            count += 1;
            continue;
        }
        else {
            max_count = max(max_count, count);
            min_count = min(min_count, count);
            count = 0;
        }
    }
 
    return (max_count - min_count);
}
 
// Driver code
int main()
{
    int arr[] = { 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << findDiff(arr, n) << "\n";
    return 0;
}

// JAVA Code for Difference between
// highest and least frequencies
// in an array
import java.util.*;
 
class GFG {
 
    static int findDiff(int arr[], int n)
    {
        // sort the array
        Arrays.sort(arr);
 
        int count = 0, max_count = 0,
            min_count = n;
 
        for (int i = 0; i < (n - 1); i++) {
 
            // checking consecutive elements
            if (arr[i] == arr[i + 1]) {
                count += 1;
                continue;
            }
            else {
                max_count = Math.max(max_count,
                                     count);
 
                min_count = Math.min(min_count,
                                     count);
                count = 0;
            }
        }
 
        return (max_count - min_count);
    }
 
    // Driver program to test above function
    public static void main(String[] args)
    {
 
        int arr[] = { 7, 8, 4, 5, 4, 1,
                      1, 7, 7, 2, 5 };
        int n = arr.length;
 
        System.out.println(findDiff(arr, n));
    }
}
 
// This code is contributed by Arnav Kr. Mandal.

# Python3 code to find the difference
# between highest nd least frequencies
 
def findDiff(arr, n):
     
    # sort the array
    arr.sort()
     
    count = 0; max_count = 0; min_count = n
    for i in range(0, (n-1)):
 
        # checking consecutive elements
        if arr[i] == arr[i + 1]:
            count += 1
            continue
        else:
            max_count = max(max_count, count)
            min_count = min(min_count, count)
            count = 0
    return max_count - min_count
 
# Driver Code
arr = [ 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5 ]
n = len(arr)
print (findDiff(arr, n))
 
# This code is contributed by Shreyanshi Arun.

// C# Code for Difference between
// highest and least frequencies
// in an array
using System;
 
class GFG {
 
    static int findDiff(int[] arr, int n)
    {
         
        // sort the array
        Array.Sort(arr);
 
        int count = 0, max_count = 0,
            min_count = n;
 
        for (int i = 0; i < (n - 1); i++) {
 
            // checking consecutive elements
            if (arr[i] == arr[i + 1]) {
                count += 1;
                continue;
            }
            else {
                max_count = Math.Max(max_count,
                                    count);
 
                min_count = Math.Min(min_count,
                                    count);
                count = 0;
            }
        }
 
        return (max_count - min_count);
    }
 
    // Driver program to test above function
    public static void Main()
    {
 
        int[] arr = { 7, 8, 4, 5, 4, 1,
                       1, 7, 7, 2, 5 };
        int n = arr.Length;
 
        Console.WriteLine(findDiff(arr, n));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP code to find the
// difference between highest
// and least frequencies
 
// function that
// returns difference
function findDiff($arr, $n)
{
     
    // sort the array
    sort($arr);
 
    $count = 0; $max_count = 0;
    $min_count = $n;
    for ($i = 0; $i < ($n - 1); $i++)
    {
 
        // checking consecutive elements
        if ($arr[$i] == $arr[$i + 1])
        {
            $count += 1;
            continue;
        }
        else
        {
            $max_count = max($max_count, $count);
            $min_count = min($min_count, $count);
            $count = 0;
        }
    }
 
    return ($max_count - $min_count);
}
 
// Driver Code
$arr = array(7, 8, 4, 5, 4, 1,
             1, 7, 7, 2, 5);
$n = sizeof($arr);
 
echo(findDiff($arr, $n) . "\n");
 
// This code is contributed by Ajit.
?>

<script>
    // Javascript Code for Difference between
    // highest and least frequencies
    // in an array
     
    function findDiff(arr, n)
    {
           
        // sort the array
        arr.sort(function(a, b){return a - b});
   
        let count = 0, max_count = 0, min_count = n;
   
        for (let i = 0; i < (n - 1); i++) {
   
            // checking consecutive elements
            if (arr[i] == arr[i + 1]) {
                count += 1;
                continue;
            }
            else {
                max_count = Math.max(max_count, count);
   
                min_count = Math.min(min_count, count);
                count = 0;
            }
        }
   
        return (max_count - min_count);
    }
     
    let arr = [ 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5 ];
    let n = arr.length;
 
    document.write(findDiff(arr, n));
         
</script>

2

Complejidad de tiempo: O(nlogn)
Complejidad de espacio: O(n)

Una solución eficiente es usar hashing. Contamos las frecuencias de todos los elementos y finalmente recorremos la tabla hash para encontrar el máximo y el mínimo.

A continuación se muestra la implementación.

// CPP code to find the difference between highest
// and least frequencies
#include <bits/stdc++.h>
using namespace std;
 
int findDiff(int arr[], int n)
{
    // Put all elements in a hash map
    unordered_map<int, int> hm;
    for (int i = 0; i < n; i++)
        hm[arr[i]]++;
 
    // Find counts of maximum and minimum
    // frequent elements
    int max_count = 0, min_count = n;
    for (auto x : hm) {
        max_count = max(max_count, x.second);
        min_count = min(min_count, x.second);
    }
 
    return (max_count - min_count);
}
 
// Driver
int main()
{
    int arr[] = { 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << findDiff(arr, n) << "\n";
    return 0;
}

// Java code to find the difference between highest
// and least frequencies
import java.util.*;
 
class GFG
{
 
static int findDiff(int arr[], int n)
{
    // Put all elements in a hash map
    Map<Integer,Integer> mp = new HashMap<>();
    for (int i = 0 ; i < n; i++)
    {
        if(mp.containsKey(arr[i]))
        {
            mp.put(arr[i], mp.get(arr[i])+1);
        }
        else
        {
            mp.put(arr[i], 1);
        }
    }
 
    // Find counts of maximum and minimum
    // frequent elements
    int max_count = 0, min_count = n;
    for (Map.Entry<Integer,Integer> x : mp.entrySet())
    {
        max_count = Math.max(max_count, x.getValue());
        min_count = Math.min(min_count, x.getValue());
    }
 
    return (max_count - min_count);
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5 };
    int n = arr.length;
    System.out.println(findDiff(arr, n));
}
}
 
/* This code is contributed by PrinciRaj1992 */

# Python code to find the difference between highest
# and least frequencies
 
from collections import defaultdict
def findDiff(arr,n):
 
    # Put all elements in a hash map
    mp = defaultdict(lambda:0)
    for i in range(n):
        mp[arr[i]]+=1
 
    # Find counts of maximum and minimum
    # frequent elements
    max_count=0;min_count=n
    for key,values in mp.items():
        max_count= max(max_count,values)
        min_count = min(min_count,values)
 
    return max_count-min_count
 
 
# Driver code
arr = [ 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5]
n = len(arr)
print(findDiff(arr,n))
 
# This code is contributed by Shrikant13

// C# code to find the difference between highest
// and least frequencies
using System;
using System.Collections.Generic;
 
class GFG
{
 
static int findDiff(int []arr, int n)
{
    // Put all elements in a hash map
    Dictionary<int,int> mp = new Dictionary<int,int>();
    for (int i = 0 ; i < n; i++)
    {
        if(mp.ContainsKey(arr[i]))
        {
            var val = mp[arr[i]];
            mp.Remove(arr[i]);
            mp.Add(arr[i], val + 1);
        }
        else
        {
            mp.Add(arr[i], 1);
        }
    }
 
    // Find counts of maximum and minimum
    // frequent elements
    int max_count = 0, min_count = n;
    foreach(KeyValuePair<int, int> entry in mp)
    {
        max_count = Math.Max(max_count, entry.Value);
        min_count = Math.Min(min_count, entry.Value);
    }
 
    return (max_count - min_count);
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5 };
    int n = arr.Length;
    Console.WriteLine(findDiff(arr, n));
}
}
 
// This code is contributed by Princi Singh

<script>
      // JavaScript code to find the difference between highest
      // and least frequencies
      function findDiff(arr, n)
      {
       
        // Put all elements in a hash map
        var mp = {};
        for (var i = 0; i < n; i++) {
          if (mp.hasOwnProperty(arr[i])) {
            var val = mp[arr[i]];
            delete mp[arr[i]];
            mp[arr[i]] = val + 1;
          } else {
            mp[arr[i]] = 1;
          }
        }
 
        // Find counts of maximum and minimum
        // frequent elements
        var max_count = 0,
          min_count = n;
        for (const [key, value] of Object.entries(mp)) {
          max_count = Math.max(max_count, value);
          min_count = Math.min(min_count, value);
        }
 
        return max_count - min_count;
      }
 
      // Driver code
      var arr = [7, 8, 4, 5, 4, 1, 1, 7, 7, 2, 5];
      var n = arr.length;
      document.write(findDiff(arr, n));
       
      // This code is contributed by rdtank.
    </script>

2

Complejidad temporal: O(n)
Espacio auxiliar: O(n)

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