Declare a map hash to store array elements as keys and to associate their frequencies with them.
Unordered_map <int, int>hash;
For each array element Insert it as key & increase frequencies. (0 ->1) For same key it will only increase frequencies.
For i=0: n-1
hash[array [i]]++;
End For
Now to print the non-repeated character we need to print the keys (array elements) having value (frequency) exactly 1. (Non-repeating) Set an iterator to hash.begin(). iterator->first is the key (array element) & iterator->second is the value( frequency of corresponding array value)
IF
Iterator->second > 1
Print iterator->first (the array element)
END IF
Time complexity: O(n)
Explanation with example:
For this array: 2 5 3 2 4 5 3 6 7 3
The code:
for(int i=0;i<n;i++){//creating the map
hash[a[i]]++;//for same key increase frequency
}
Actually does the following
At i=0array[i]=2
Insert 2 & increase frequency
Hash:
Key(element) Value(frequency)
2 1
At i=1array[i]=5
Insert 5 & increase frequency
Hash:
Key(element) Value(frequency)
2 1
5 1
At i=2array[i]=3
Insert 3 & increase frequency
Hash:
Key(element) Value(frequency)
2 1
5 1
3 1
At i=3array[i]=2
Insert 2 increase frequency
'2' is already there, thus frequency increase.
Hash:
Key(element) Value(frequency)
2 2
5 1
3 1
At i=4array[i]=4
Insert 4 &increase frequency
Hash:
Key(element) Value(frequency)
2 2
5 1
3 1
4 1
At i=5array[i]=5
'5' is already there, thus frequency increase.
Hash:
Key(element) Value(frequency)
2 2
5 2
3 1
4 1
At i=6array[i]=3
'3' is already there, thus frequency increase.
Hash:
Key(element) Value(frequency)
2 2
5 2
3 2
4 1
At i=7array[i]=6
Insert 6, increase frequency.
Hash:
Key(element) Value(frequency)
2 2
5 2
3 2
4 1
6 1
At i=8array[i]=7
Insert 7, increase frequency.
Hash:
Key(element) Value(frequency)
2 2
5 2
3 2
4 1
6 1
7 1
At i=9array[i]=3
'3' is already there, thus frequency increase.
Hash:
Key(element) Value(frequency)
2 2
5 2
3 3
4 1
6 1
7 1
Thus, Elements with frequency 1 are: 7, 6, 4
C++ implementation to print all the Non-Repeated Numbers with Frequency in an Array
#include <bits/stdc++.h>
using namespace std;
void findNonRepeat(int* a, int n){
//Declare the map
unordered_map<int,int> hash;
for(int i=0;i<n;i++){//creating the map
hash[a[i]]++;//for same key increase frequency
}
cout<<"the nonrepeating numbers are: ";
//iterator->first == key(element value)
//iterator->second == value(frequency)
for(auto it=hash.begin();it!=hash.end();it++)
if(it->second==1)//frequency==1 means non-repeating element
printf("%d ",it->first);
printf("\n");
}
int main()
{
int n;
cout<<"enter array length\n";
cin>>n;
int* a=(int*)(malloc(sizeof(int)*n));
cout<<"input array elements...\n";
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
//function to print repeating elements with their frequencies
findNonRepeat(a,n);
return 0;
}
Data structures used:
Algorithm:
Insert it as key & increase frequencies. (0 ->1)
For same key it will only increase frequencies.
Set an iterator to hash.begin().
iterator->first is the key (array element) & iterator->second is the value( frequency of corresponding array value)
Time complexity: O(n)
Explanation with example:
For this array: 2 5 3 2 4 5 3 6 7 3
The code:
Actually does the following
Thus, Elements with frequency 1 are: 7, 6, 4
C++ implementation to print all the Non-Repeated Numbers with Frequency in an Array
Output