Find frequency of each element in an Array in C++
In this tutorial, we are going to see how to frequency of each element in an Unsorted array in C++.
There are many ways to solve this problem, in this tutorial we will see the brute force approach and the most optimized approach that is hashing.
The arrangement of the elements in the array will be random.
Example:
Input -> {3,4,3,5,5,1,1,1,2,2,4} //Elements along with their frequency is displayed Output: 3 -> 2 times 4 -> 2 times 5 -> 2 times 1 -> 3 times 2 -> 2 times
C++ program to find the frequency of elements in an Array
BRUTE FORCE
In this we will use the classical approach to every problem, that is to solve using nested loops.
For this problem, we will use two loops one for picking an element and another for counting its frequency, this is a simple approach and can easily be implemented.
Time Complexity = O(n²)
Space Complexity = O(n)
Where,
n -> size of the array
USING HASHING
In this technique, we will use a map to store the count of each element. We can use a map if we want to store elements along with their frequency in a sorted fashion else we can use unordered_map.
Let’s see the implementation.
IMPLEMENTATION
#include <bits/stdc++.h> using namespace std; //using unordered_map to count and store frequency void frequencyUnorderedMap(vector<int> a) { unordered_map<int, int> mp; //storing elements along with their frequency in unordered_map for (int i = 0; i < a.size(); i++) mp[a[i]]++; unordered_map<int, int>::iterator i; cout << "When unordered_map is used\n"; //displaying elements along with their frequency //i->first is element & i->second is its frequnecy for (i = mp.begin(); i != mp.end(); i++) cout << i->first << " -> " << i->second << " times\n"; cout << "\n"; } //using map to count and store frequency void frequencyMap(vector<int> a) { map<int, int> mp; //storing elements along with their frequency in map for (int i = 0; i < a.size(); i++) mp[a[i]]++; map<int, int>::iterator i; cout << "When map is used\n"; //displaying elements along with their frequency //i->first is element & i->second is its frequnecy for (i = mp.begin(); i != mp.end(); i++) cout << i->first << " -> " << i->second << " times\n"; } int main() { int n; cout << "Enter the size of the array: "; cin >> n; vector<int> a(n); cout << "Enter elements of the array: "; for (int i = 0; i < n; i++) cin >> a[i]; cout << "\n"; frequencyUnorderedMap(a); frequencyMap(a); return 0; }
INPUT/OUTPUT
Enter the size of the array: 11 Enter elements of the array: 3 4 3 5 5 1 1 1 2 2 4 When unordered_map is used 2 -> 2 times 1 -> 3 times 5 -> 2 times 3 -> 2 times 4 -> 2 times When map is used 1 -> 3 times 2 -> 2 times 3 -> 2 times 4 -> 2 times 5 -> 2 times
Time Complexity:
frequencyUnorderedMap = O(n)
frequencyMap = O(nlogn)
Space Complexity = O(n)
Where,
n -> size of the array
Leave a Reply