contains Duplicate Algorithm
The Contains Duplicate Algorithm is a widely used programming approach to efficiently determine if an array or list contains any duplicate elements. This algorithm is highly useful in various applications such as data validation, database queries, and network security. The essential idea behind this algorithm is to utilize data structures like sets or hash tables to store unique elements as they are encountered while iterating through the given array. If an element is found to already exist in the set or hash table, it signifies that the array contains a duplicate element, and the algorithm can return a corresponding result.
In a typical implementation of the Contains Duplicate Algorithm, a programmer would start by creating an empty set or hash table to store unique elements. Next, they would iterate through the input array or list, checking the set or hash table for the presence of each element. If the element is not present in the set, it is added. If the element is already found in the set, it indicates a duplicate element, and the algorithm can return true immediately. If the entire array is iterated through without finding any duplicates, the algorithm returns false. This approach generally has a time complexity of O(n) and a space complexity of O(n) as well, where 'n' represents the number of elements in the input array.
/**
* Given an array of integers, find if the array contains any duplicates.
* Your function should return true if any value appears at least twice in the array,
* and it should return false if every element is distinct.
*
* Approach : sort and check for adjacent elements for duplicates.
*
*/
#include <iostream>
#include <vector>
#include <algorithm>
bool containsDuplicate(std::vector<int>& nums) {
std::sort( nums.begin(), nums.end());
for ( size_t i = 1; i < nums.size(); ++i ) {
if ( nums[i-1] == nums[i] ) {
return true;
}
}
return false;
}
void printVect( std::vector<int> & vec ) {
std::cout << "VEC:";
for ( auto & i : vec ) {
std::cout << i << " ";
}
std::cout << std::endl;
}
int main() {
std::vector<int> vec1{ 1, 99, 99, 4, 8, 98, 96, 3, 5, 19, 23, 17, 84, 23 };
printVect(vec1);
if ( containsDuplicate(vec1) ) {
std::cout << "Above vector contains duplicates\n";
} else {
std::cout << "Above vector does not contain duplicates\n";
}
return 0;
}
