CODEWITHSUNDEEP
c++algorithmc++11c++14c++17
user1899020
user1899020

Reputation: 13575

Find the unique elements of a vector C++

Is there a fast way to find all the single elements (only appeared once) in a vector of elements? All the elements in the vector is either single or dual (appeared twice). My answer is sort all the elements and then remove double appeared elements. Any faster way to do it?

Upvotes: 4

Views: 10895

Answers (2)

Photon
Photon

Reputation: 2777

So for small enough n (<=1e8) sorting and removal (using std::sort() and std::unique) approach is still faster than hash tables.

Sample code: O(n log n)

vector<int>A = {1,2,3,1,2,5};
    sort(A.begin(),A.end());
    A.erase(unique(A.begin(),A.end()),A.end());
    for(int&x:A)
        cout<<x<<" ";

Upvotes: 4

Chemistree
Chemistree

Reputation: 432

if your elements are hashable, you can use a std::unordered_map<T, int> to store the count of each element, which will take amortized linear time:

template<typename T>
std::vector<T> uniqueElements(const std::vector<T>& v) {
    std::unordered_map<T, int> counts;
    for(const auto& elem : v) ++counts[elem];
    std::vector<T> result;
    for(auto [elem, count] : counts)
        if(count == 1)
            result.push_back(elem);
    return result;
}

For small lists, sorting and then doing a linear pass might still be faster. Also note that this copies your elements, which might also be expensive in some cases

Upvotes: 1

Related Questions