CODEWITHSUNDEEP
c++vectorduplicateselement
TDNguyen
TDNguyen

Reputation: 23

Deleting both an element and its duplicates in a Vector in C++

I've searched the Internet and known how to delete an element (with std::erase) and finding duplicates of an element to then delete it (vec.erase(std::unique(vec.begin(), vec.end()),vec.end());). But all methods only delete either an element or its duplicates.

I want to delete both.

For example, using this vector: std::vector<int> vec = {2,3,1,5,2,2,5,1};

I want output to be: {3}

My initial idea was:

void removeDuplicatesandElement(std::vector<int> &vec)
{
    std::sort(vec.begin(), vec.end());
    int passedNumber = 0;  //To tell amount of number not deleted (since not duplicated)
    for (int i = 0; i != vec.size(); i = passedNumber)    //This is not best practice, but I tried
    {
        if (vec[i] == vec[i+1])
        {
            int ctr = 1;
            for(int j = i+1; j != vec.size(); j++)
            {
                if (vec[j] == vec[i]) ctr++;
                else break;
            }
            vec.erase(vec.begin()+i, vec.begin()+i+ctr);
        }
        else passedNumber++;
    }
}

And it worked. But this code is redundant and runs at O(n^2), so I'm trying to find other ways to solve the problem (maybe an STL function that I've never heard of, or just improve the code).

Upvotes: 0

Views: 346

Answers (3)

Hoang
Hoang

Reputation: 177

From what you have searched, we can look in the vector for duplicated values, then use the Erase–remove idiom to clean up the vector.

#include <vector>
#include <algorithm>
#include <iostream>

void removeDuplicatesandElement(std::vector<int> &vec)
{
    std::sort(vec.begin(), vec.end());

    if (vec.size() < 2)
        return;

    for (int i = 0; i < vec.size() - 1;)
    {
        // This is for the case we emptied our vector
        if (vec.size() < 2)
            return;

        // This heavily relies on the fact that this vector is sorted
        if (vec[i] == vec[i + 1])
            vec.erase(std::remove(vec.begin(), vec.end(), (int)vec[i]), vec.end());
        else
            i += 1;
    }

    // Since all duplicates are removed, the remaining elements in the vector are unique, thus the size of the vector
    // But we are not returning anything or any reference, so I'm just gonna leave this here
    // return vec.size()
}

int main()
{
    std::vector<int> vec = {2, 3, 1, 5, 2, 2, 5, 1};
    removeDuplicatesandElement(vec);

    for (auto i : vec)
    {
        std::cout << i << " ";
    }
    std::cout << "\n";

    return 0;
}

Output: 3

Time complexity: O(n)

Upvotes: 1

ubaid shaikh
ubaid shaikh

Reputation: 453

You can do it using STL maps as follows:

#include <iostream>
#include <vector>
#include <unordered_map>


using namespace std;

void retainUniqueElements(vector<int> &A){
    unordered_map<int, int> Cnt;
    for(auto element:A) Cnt[element]++;
    A.clear();  //removes all the elements of A
    for(auto i:Cnt){
        if(i.second == 1){   // that if the element occurs once
            A.push_back(i.first);  //then add it in our vector
        }
    }
}

int main() {
    vector<int> vec = {2,3,1,5,2,2,5,1};
    retainUniqueElements(vec);
    
    for(auto i:vec){
        cout << i << " ";
    }
    cout << "\n";

    return 0;
}

Output:

3

Time Complexity of the above approach: O(n)

Space Complexity of the above approach: O(n)

Upvotes: 1

Igor Tandetnik
Igor Tandetnik

Reputation: 52471

Something like this, perhaps:

void removeDuplicatesandElement(std::vector<int> &vec) {
    if (vec.size() <= 1) return;
    std::sort(vec.begin(), vec.end());
    int cur_val = vec.front() - 1;
    auto pred = [&](const int& val) {
        if (val == cur_val) return true;
        cur_val = val;
        // Look ahead to the next element to see if it's a duplicate.
        return &val != &vec.back() && (&val)[1] == val;
    };
    vec.erase(std::remove_if(vec.begin(), vec.end(), pred), vec.end());
}

Demo

This relies heavily on the fact that std::vector is guaranteed to have contiguous storage. It won't work with any other container.

Upvotes: 2

Related Questions