Check for duplicates in a C++ array
This post will discuss how to check for duplicates in an array in C++.
1. Using Set
A simple and elegant solution is to construct a set from the array which retains only distinct elements. Then simply compare the set’s size against the array’s length. If both are not the same, then we can say that the array contains duplicates. This works in linear time and space.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> #include <unordered_set> #include <iterator> int main() { int arr[] = {1, 3, 5, 7, 3, 9}; int n = sizeof(arr) / sizeof(*arr); std::unordered_set<int> distinct(std::begin(arr), std::end(arr)); bool hasDuplicates = n != distinct.size(); if (hasDuplicates) { std::cout << "Array contains duplicates"; } else { std::cout << "Array contains no duplicates"; } return 0; } |
Output:
Array contains duplicates
2. Using Sorting
Another option is to sort the array and compare each pair of consecutive elements to check for duplicates. This works in O(nlog(n)) time if the standard sorting algorithm is used. This would translate to the following code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> #include <algorithm> #include <iterator> int main() { int arr[] = {1, 3, 5, 7, 3, 9}; std::size_t n = std::distance(std::begin(arr), std::end(arr)); bool hasDuplicates = false; std::sort(std::begin(arr), std::end(arr)); for (int i = 0; i < n - 1; i++) { if (arr[i] == arr[i + 1]) { hasDuplicates = true; } } if (hasDuplicates) { std::cout << "Array contains duplicates"; } else { std::cout << "Array contains no duplicates"; } return 0; } |
Output:
Array contains duplicates
3. Using std::adjacent_find
A better solution is to use std::adjacent_find to find the first occurrence of equal adjacent elements in the sorted array. It returns an iterator to the first duplicate elegant, or end of the range if no duplicate is found.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> #include <algorithm> int main() { int arr[] = {1, 3, 5, 7, 3, 9}; int n = sizeof(arr) / sizeof(*arr); std::sort(arr, arr + n); bool hasDuplicates = std::adjacent_find(arr, arr + n) != arr + n; if (hasDuplicates) { std::cout << "Array contains duplicates"; } else { std::cout << "Array contains no duplicates"; } return 0; } |
Output:
Array contains duplicates
With C++11, we can get an iterator to the beginning and end of the array:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> #include <algorithm> #include <iterator> int main() { int arr[] = {1, 3, 5, 7, 3, 9}; std::size_t n = std::distance(std::begin(arr), std::end(arr)); std::sort(std::begin(arr), std::end(arr)); bool hasDuplicates = std::adjacent_find(std::begin(arr), std::end(arr)) != std::end(arr); if (hasDuplicates) { std::cout << "Array contains duplicates"; } else { std::cout << "Array contains no duplicates"; } return 0; } |
Output:
Array contains duplicates
4. Using std::unique function
Alternatively, we can use the std::unique function to remove consecutive duplicates after sorting the array. It can be used as follows:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> #include <algorithm> int main() { int arr[] = {1, 3, 5, 7, 3, 9}; int n = sizeof(arr) / sizeof(*arr); std::sort(arr, arr + n); bool hasDuplicates = std::unique(arr, arr + n) != arr + n; if (hasDuplicates) { std::cout << "Array contains duplicates"; } else { std::cout << "Array contains no duplicates"; } return 0; } |
Output:
Array contains duplicates
With C++11, we can get an iterator to the beginning and end of the array:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> #include <algorithm> #include <iterator> int main() { int arr[] = {1, 3, 5, 7, 3, 9}; std::size_t n = std::distance(std::begin(arr), std::end(arr)); std::sort(std::begin(arr), std::end(arr)); bool hasDuplicates = std::unique(std::begin(arr), std::end(arr)) != std::end(arr); if (hasDuplicates) { std::cout << "Array contains duplicates"; } else { std::cout << "Array contains no duplicates"; } return 0; } |
Output:
Array contains duplicates
That’s all about checking for duplicates in an array in C++.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)