CODEWITHSUNDEEP
c++algorithmsortingvectorstl
user13725909
user13725909

Reputation:

How to remove 'all duplicated ' values?

There`s a lot of tutorials exist for removing duplicate values and I have checked all

like

{1,2,3,4,1,2,3,4,5} -> {1,2,3,4,5}

by using sort(), unique() function.

but if I want to remove 'all duplicated' values

like

{1,2,3,4,1,2,3,4,5} -> {5}

How to implement it?

I have manually split the original vector into two parts and remove the duplicated elements in first one by later one.

It makes sense but if the original vector size became huge, then I cannot split the original vector manually.

Upvotes: 3

Views: 942

Answers (5)

cigien
cigien

Reputation: 60440

Here's a solution using range-v3:

namespace rv = ranges::views;
    
ranges::sort(v);
   
auto res = v 
      | rv::group_by(std::equal_to{}) 
      | rv::filter([](auto r) { return ranges::size(r) == 1; }) 
      | rv::join
      | ranges::to<std::vector<int>>;

Here's a demo.

Here's an O(n log(n)) in-place solution, using the STL:

auto begin = v.begin(), end = v.end();
    
std::sort(begin, end);

while(begin != end)
  if (auto f = std::find_if(begin + 1, end, 
                 [begin](int i) { return i != *begin; });
      begin + 1 != f)  // if duplicate elements found
    end = std::move(f, end, begin);   // move them to the end
  else ++begin;
  
v.erase(end, v.end());

Here's a demo.

Upvotes: 4

Daniel
Daniel

Reputation: 7724

An unordered_map should deal with the case:

#include <iostream> 
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int arr[] = {1,2,3,4,1,2,3,4,5};
    int n = 9;
    unordered_map<int, int> counter;

    for(int i = 0; i < n; i++){
        counter[arr[i]]++;
    }
    
    vector<int> ans;
    
    for (auto& it: counter) {
        if(it.second == 1) ans.push_back(it.first);
    }
    
    for(int i = 0; i < ans.size(); i++) cout<<ans[i]<<" ";
    return 0;
}

It simply counts the occurrences of the elements of the array. If the occurrence count of an element is 1, it is unique, so you store it in a vector or array (of the size of the map).

Complexity: O(n) time and space.

You can also use unordered_multiset, since it stores the element count as well.

Upvotes: 1

A M
A M

Reputation: 15265

I am sorry that I basically repeat the answer of user Daniel, but because I saw the first 2 lines of his code, I have to. I am sorry.

So, what you actually want, and that should be the question, is: How can I get the values in an array that occur exactly once?

And that question leads you already to the answer. You need to count the occurences of each value in an array. And that can easily be done using a std::map or a std::unordered map.

It has a index operator [] which does the following:

Returns a reference to the value that is mapped to a key equivalent to key, performing an insertion if such key does not already exist.

Please see here for details.

So, in any way, it will return a refence to a value in the std::map. And with the post increment operator we will do the count.

Then we can simply show the result on the screen, resulting in a really very compact program:

#include <iostream>
#include <map>
#include <vector>

int main() {
    // The test data
    std::vector values{ 1,2,3,4,1,2,3,4,5 };

    // We will count all instances of values
    std::map<int, size_t> counter{};
    for (const int i : values) counter[i]++;

    // Display the result
    for (const auto& [value, count] : counter) 
        if (1==count) std::cout << value << '\n';

    return 0;
}

If you want to have the result in a different std::vector, then you can simply use a small for loop and push_back the values with a count of 1.

Upvotes: 0

Nimantha Fernando
Nimantha Fernando

Reputation: 393

#include<iostream>
#include<vector>

using namespace std;

int main()
{
    vector<int> list = { 1,2,3,4,1,2,3,4,5 };
    vector<int> rest;
    

    for (int i = 0; i < list.size(); i++) {
        int count = 0;
        for (int j = 0; j < list.size(); j++) {
            if (list[i] == list[j]) {
                count++;
                
            }
        }
        if (count == 1) {
            rest.push_back(list[i]);
        }
    }

    for (int i = 0; i < rest.size(); i++) {
        cout << rest[i] << " ";
    }

    cout << endl;

    return 0;
}

simply you just need to use 2 for loops for the implementation.

Upvotes: -1

Marshall Clow
Marshall Clow

Reputation: 16700

My advice: Don't try to do it in-place.

I would sort the vector, and then make a pass through, identifying elements that occur more than once (which should be easy, since they're now adjacent), and writing those that do not into another vector.

An interface similar to copy_if

OutIter copy_unique(Iterator first, Iterator last, OutIter out);

That is an O(n log n + n) solution.

An in-place solution (like @william_ suggests) would be O(N^2)

Upvotes: 2

Related Questions