By idiot_grad_student


2020-06-30 03:05:25 8 Comments

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.

5 comments

@cigien 2020-06-30 04:37:28

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.

@NoSenseEtAl 2020-07-01 10:35:07

Nice, but I have a question: can it be done inplace (in vector v) using ranges?

@cigien 2020-07-02 01:05:16

@NoSenseEtAl It's possible, but nothing comes to mind.

@cigien 2020-07-02 14:20:15

@NoSenseEtAl Added an in-place solution as well.

@NoSenseEtAl 2020-07-02 18:04:53

thank you, cant upvote since I already upvoted before :)

@Daniel 2020-06-30 03:29:13

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.

@sweenish 2020-06-30 04:06:45

Those first two lines make for a bad answer.

@Pete Becker 2020-06-30 13:56:28

<bits/stdc++.h> is not part of standard C++.

@Armin Montigny 2020-06-30 06:37:38

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.

@nimantha fernando 2020-06-30 04:10:10

#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.

@PaulMcKenzie 2020-06-30 05:36:01

Now imagine if there were 10000 elements -- You would loop 100000000 times. The OP specified that the array can become large.

@nimantha fernando 2020-06-30 06:00:53

we have to use a map,

@Marshall Clow 2020-06-30 03:22:14

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)

@BessieTheCow 2020-06-30 03:28:38

O(n log n + n) = O(n log n), and it is possible to do it in-place in O(n log n) by first sorting and then removing elements which occur more than once in a similar manner to std::remove.

@Marshall Clow 2020-06-30 04:51:40

Sure it's possible to do it in place; but it's easier if you can make a copy of the non-duplicated elements. Hence my "advice"

Related Questions

Sponsored Content

47 Answered Questions

[SOLVED] Sort array of objects by string property value

53 Answered Questions

79 Answered Questions

[SOLVED] How do I iterate over the words of a string?

  • 2008-10-25 08:58:21
  • Ashwin Nanjappa
  • 2183413 View
  • 2999 Score
  • 79 Answer
  • Tags:   c++ string split

49 Answered Questions

[SOLVED] Removing duplicates in lists

36 Answered Questions

[SOLVED] How can I pair socks from a pile efficiently?

28 Answered Questions

[SOLVED] How do you set, clear, and toggle a single bit?

9 Answered Questions

[SOLVED] Swift Beta performance: sorting arrays

57 Answered Questions

[SOLVED] Sort a Map<Key, Value> by values

34 Answered Questions

[SOLVED] How do I sort a dictionary by value?

18 Answered Questions

Sponsored Content