intersection of array Algorithm
The intersection of array algorithm is a technique used in computer science to find the common elements between two or more arrays. This algorithm is widely used in various applications such as database management systems, data mining, and statistical analysis, where finding commonalities between datasets is essential. The primary goal of the intersection algorithm is to identify the elements that are present in all the input arrays and return them as a new array, which represents the intersection.
There are several approaches to implementing the intersection of array algorithm, with each having its pros and cons. One common method is the "hashing" technique, where the algorithm iterates through each element in the first array, storing them in a hash table or a set. Then, it iterates through the second array, checking if the element exists in the hash table or set. If it does, the element is added to the intersection result array. This process can be extended to multiple arrays, where each subsequent array is checked for the presence of elements in the hash table or set. Another approach is the "sorting and merging" technique, where the input arrays are first sorted, and then a merge-like operation is performed to find the common elements. The choice of implementation depends on factors such as the size of the arrays, the need for performance optimization, and the desired trade-offs between time and space complexity.
/*
* Find intersection of two arrays/vectors:
* Given two vectors find the result of their interaction.
* The result should only contain unique characters and can be in any order.
*
* [1 2 3 3 4 4 5 5]
* [2 3 5 5 4 4 6]
* Result: [2 3 5 4] or [2 3 4 5]
*/
#include <iostream>
#include <vector>
#include <unordered_set>
std::vector<int> find_intersection(const std::vector<int>& vec1,
const std::vector<int>& vec2)
{
std::vector<int> result;
std::unordered_set<int> set(vec1.begin(), vec1.end());
for (int num : vec2) {
if (set.erase(num)) {
result.push_back(num);
}
}
return result;
}
template <typename T>
void print_vector(const std::vector<T>& vec) {
for (auto n: vec) {
std::cout << n << " ";
}
std::cout << std::endl;
}
int main()
{
std::vector<int> vec1 {1, 2, 3, 3, 4, 4, 5, 5};
std::vector<int> vec2 {2, 3, 5, 5, 4, 4, 6};
std::cout << "Vec 1: ";
print_vector(vec1);
std::cout << "Vec 2: ";
print_vector(vec2);
std::vector<int> result = find_intersection(vec1, vec2);
std::cout << "Result: ";
print_vector(result);
return 0;
}
