More elegant way to check for duplicates in C++ array?

user_425780 0
Viewed 102877

I wrote this code in C++ as part of a uni task where I need to ensure that there are no duplicates within an array:

// Check for duplicate numbers in user inputted data
    int i; // Need to declare i here so that it can be accessed by the 'inner' loop that starts on line 21
    for(i = 0;i < 6; i++) { // Check each other number in the array
        for(int j = i; j < 6; j++) { // Check the rest of the numbers
            if(j != i) { // Makes sure don't check number against itself
                if(userNumbers[i] == userNumbers[j]) {
                    b = true;
                }
            }
            if(b == true) { // If there is a duplicate, change that particular number
                cout << "Please re-enter number " << i + 1 << ". Duplicate numbers are not allowed:" << endl;
                cin >> userNumbers[i];
            }
        } // Comparison loop
        b = false; // Reset the boolean after each number entered has been checked
    } // Main check loop

It works perfectly, but I'd like to know if there is a more elegant or efficient way to check.

duplicates arrays c++
13 Answers

I think @Michael Jaison G's solution is really brilliant, I modify his code a little to avoid sorting. (By using unordered_set, the algorithm may faster a little.)

template <class Iterator>
bool isDuplicated(Iterator begin, Iterator end) {
    using T = typename std::iterator_traits<Iterator>::value_type;
    std::unordered_set<T> values(begin, end);
    std::size_t size = std::distance(begin,end);
    return size != values.size();
}
user_99314480 
#include<iostream>
#include<algorithm>

int main(){

    int arr[] = {3, 2, 3, 4, 1, 5, 5, 5};
    int len = sizeof(arr) / sizeof(*arr); // Finding length of array

    std::sort(arr, arr+len);

    int unique_elements = std::unique(arr, arr+len) - arr;

    if(unique_elements == len) std::cout << "Duplicate number is not present here\n";
    else std::cout << "Duplicate number present in this array\n";

    return 0;
}
user_60855210

As mentioned by @underscore_d, an elegant and efficient solution would be,

#include <algorithm>
#include <vector>

template <class Iterator>
bool has_duplicates(Iterator begin, Iterator end) {
    using T = typename std::iterator_traits<Iterator>::value_type;
    std::vector<T> values(begin, end);

    std::sort(values.begin(), values.end());
    return (std::adjacent_find(values.begin(), values.end()) != values.end());
}

int main() {
    int user_ids[6];
    // ...
    std::cout << has_duplicates(user_ids, user_ids + 6) << std::endl;
}
user_31526000

fast O(N) time and space solution return first when it hits duplicate

template <typename T>
bool containsDuplicate(vector<T>& items) {
    return any_of(items.begin(), items.end(), [s = unordered_set<T>{}](const auto& item) mutable {
        return !s.insert(item).second;
    });
}
user_87621980

Not enough karma to post a comment. Hence a post.

   vector <int> numArray = { 1,2,1,4,5 };
   unordered_map<int, bool> hasDuplicate;
   bool flag = false;
   for (auto i : numArray)
   {
      if (hasDuplicate[i])
      {
         flag = true;
         break;
      }
      else
         hasDuplicate[i] = true;
   }

   (flag)?(cout << "Duplicate"):("No duplicate");
user_42231050
Related