Programa C++ para el elemento menos frecuente en una array

Dada una array, encuentre el elemento menos frecuente en ella. Si hay varios elementos que aparecen la menor cantidad de veces, imprima cualquiera de ellos.
Ejemplos: 
 

Input : arr[] = {1, 3, 2, 1, 2, 2, 3, 1}
Output : 3
3 appears minimum number of times in given
array.

Input : arr[] = {10, 20, 30}
Output : 10 or 20 or 30

Una solución simple es ejecutar dos bucles. El bucle exterior recoge todos los elementos uno por uno. El bucle interno encuentra la frecuencia del elemento elegido y la compara con el mínimo hasta el momento. La complejidad temporal de esta solución es O(n ² )
Una mejor solución es clasificar. Primero ordenamos la array, luego recorremos linealmente la array.
 

// CPP program to find the least frequent element
// in an array.
#include <bits/stdc++.h>
using namespace std;
  
int leastFrequent(int arr[], int n)
{
    // Sort the array
    sort(arr, arr + n);
  
    // find the min frequency using linear traversal
    int min_count = n+1, res = -1, curr_count = 1;
    for (int i = 1; i < n; i++) {
        if (arr[i] == arr[i - 1])
            curr_count++;
        else {
            if (curr_count < min_count) {
                min_count = curr_count;
                res = arr[i - 1];
            }
            curr_count = 1;
        }
    }
   
    // If last element is least frequent
    if (curr_count < min_count)
    {
        min_count = curr_count;
        res = arr[n - 1];
    }
  
    return res;
}
  
// driver program
int main()
{
    int arr[] = {1, 3, 2, 1, 2, 2, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << leastFrequent(arr, n);
    return 0;
}

3

Complejidad de tiempo: O(n Log n) 
Espacio auxiliar: O(1)
Una solución eficiente es usar hashing. Creamos una tabla hash y almacenamos elementos y su frecuencia cuenta como pares de valores clave. Finalmente recorremos la tabla hash e imprimimos la clave con el valor mínimo.
 

// CPP program to find the least frequent element
// in an array.
#include <bits/stdc++.h>
using namespace std;
  
int leastFrequent(int arr[], int n)
{
    // Insert all elements in hash.
    unordered_map<int, int> hash;
    for (int i = 0; i < n; i++)
        hash[arr[i]]++;
  
    // find the min frequency
    int min_count = n+1, res = -1;
    for (auto i : hash) {
        if (min_count >= i.second) {
            res = i.first;
            min_count = i.second;
        }
    }
  
    return res;
}
  
// driver program
int main()
{
    int arr[] = {1, 3, 2, 1, 2, 2, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << leastFrequent(arr, n);
    return 0;
}

3

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

Consulte el artículo completo sobre el elemento menos frecuente en una array para obtener más detalles.