How to remove all instances of a duplicate from a vector<int>

user_11096581 0
Viewed 158

I've been trying to solve an "easy" leetcode question for two hours now where I need to remove every instance of an int that appears more than once then add the non dupes together. I've tried about 10 different ways and I can only get it to go down to one copy of each int. Here is the nicest solution I've written, but given input {1,2,2,3,4} it would return {1,2,3,4} whereas the expected output is {1,3,4}

  sort(nums.begin(), nums.end()); //Sort numerically
  nums.erase(unique(nums.begin(), nums.end()), nums.end()); 
  return (accumulate(nums.begin(), nums.end(), 0));
stdvector vector data-structures algorithm c++
6 Answers

NlogN complexity, you avoid needing to pre-sort:

Godbolt

#include <set>
#include <vector>

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

    std::multiset<int> m (nums.begin(), nums.end());

    std::size_t sum = 0;
    for (const auto& elem : m)
    {
      sum += m.count(elem) == 1 ? elem : 0;
    }
}

Update: Could use std::unordered_multiset, as we don't need ordering.

user_34769540

You can use a std::unordered_map<int, bool> where the second (template) parameter (bool) specifies whether the value is duplicated or not. It'll look something like this,

#include <unordered_map>
...

std::unordered_map<int, bool> uniqueCheckMap;
for (auto i : nums)
{
    if (uniqueCheckMap.find(i) == uniqueCheckMap.end())
        uniqueCheckMap[i] = false;
    else
        uniqueCheckMap[i] = true;    // Set the second (value) as true if duplicate entry is found.
}

nums.clear();
int sum = 0;
for (auto i : uniqueCheckMap)
{
    if (!i.second)
    {
        nums.push_back(i.first);
        sum += i.first;
    }
}
user_112280290

There are many workarounds, you can iterate over the array and see how many time the number exists using map or something, and then you iterate again over the map and add the number that only appeared once to a new array. You can use a set and a map<bool,int>, every time you add a new number you check if it exists or not.

if(!map[number]){
set.insert(number);
map[number]=true;
}else{
set.erase(number);
}
user_126185670

If O(n²) is not a problem...

const auto sum=std::accumulate(cbegin(nums), cend(nums), 0,
  [&](const auto &accum, const auto &elem)
  {
    return accum+(std::count(cbegin(nums), cend(nums), elem)>1 ? 0 : elem);
  });
user_115270760

set_difference is a great help here. It removes occurences in the way you describe.

        auto ints = vector{4, 3, 2, 2, 1};

        sort(begin(ints), end(ints));
        std::vector<int> unique_ints;
        unique_copy(begin(ints), end(ints), back_inserter(unique_ints));

        vector<int> doubles;
        set_difference( begin(ints), end(ints),
                        begin(unique_ints), end(unique_ints),
                        back_inserter(doubles)
                        );

        vector<int> only_once;
        set_difference( begin(unique_ints), end(unique_ints),
                        begin(doubles), end(doubles),
                        back_inserter(only_once));

        copy(begin(only_once), end(only_once), ostream_iterator<int>(cout, ", "));
        cout << "\n";

Also... it seems to do the trick.

$ g++ -std=c++17 u.cpp  && ./a.out 
1, 3, 4,
xtofl_66100

Or you could use a loop over 'equal ranges', only accumulating the ones that are a single element long:

        sort(begin(ints), end(ints));

        int acc = 0;
        auto range = equal_range(begin(ints), end(ints), ints.front());

        while(range.first != end(ints)) {
                cout << *range.first << "+ ";
                if (distance(range.first, range.second) == 1){
                        acc += *range.first;
                }
                range = equal_range(range.second, end(ints), *range.second);
        }
        cout << " = " << acc << "\n";
xtofl_66100
Related