first non repeating int Algorithm
The first non-repeating integer algorithm is an efficient technique used in computer science and programming to identify the first unique integer in a given sequence or array of integers. This problem is commonly encountered in various applications, such as data analysis, machine learning, and natural language processing, where identifying unique elements in a dataset is crucial for further processing and analysis. The algorithm aims to find the first integer in the input sequence that occurs only once and does not repeat itself.
To implement this algorithm, a common approach is to utilize a data structure known as a hash table or dictionary, which allows for constant-time lookups and insertions. The algorithm begins by iterating through the input sequence and populating the hash table with the frequency count of each integer encountered. Once the frequency count has been recorded for all integers, the algorithm again iterates through the input sequence, this time checking the frequency count in the hash table. The first integer found with a frequency count of 1 is the first non-repeating integer in the sequence. This two-pass approach allows for an efficient O(n) time complexity, where n is the size of the input sequence, ensuring a fast and effective solution to the problem.
/*
* Given an array of integers, determine the first non repeating integer in the array.
*/
#include<iostream>
#include<map>
int nonRepeating(int *arr, int size){
std::map<int, int> m;
std::map<int,int>::iterator it;
for(int i = 0; i < size; ++i){
it = m.find(arr[i]);
if( it != m.end()){
m[arr[i]] = ++(it->second);
}
else{
m[arr[i]] = 1;
}
}
for(int i = 0; i < size; ++i){
it = m.find(arr[i]);
if( it != m.end()){
if(it->second == 1)
return arr[i];
}
}
return -1;
}
int main(){
int size;
int *arr;
std::cout<<"Enter size:";
std::cin>>size;
arr = new int[size];
std::cout<<"Enter contents of array:";
for(int i = 0; i < size; ++i){
std::cin>>arr[i];
}
std::cout<<"First Non repeating integer in array:"<< nonRepeating(arr,size)<<std::endl;
delete[] arr;
return 0;
}
