LeetCode remove Duplicates in c++

Question

The leetCode question want us to remove duplicates, and return the final array. I just don't know why mine has runtime error. I haven't used c++ for a while, but I checked online docks and the erase function worked as I intended. Could anyone help me with it?

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
    if(nums.size()==0)
        return 0;

for(vector<int>::iterator iter = nums.begin();iter!=nums.end();iter++)
  {
      if(*iter == *(iter+1))
      {
          nums.erase(iter+1);
          iter++;
     }

  }
    return nums.size();
}
};

You have to be careful when you erase elements while iterating over a container. The example here should give you proper code: https://en.cppreference.com/w/cpp/container/vector/erase — drescherjm, Oct 01 '18 at 22:37
We need the definition of duplicate (repeated consecutively or repeated anywhere) and whether or not ordering must be preserved to provide a reasonable solution. — user4581301, Oct 01 '18 at 23:11

Yucel_K · Answer 1 · 2018-10-01T23:19:22.417

1

you are incrementing the iter twice in your loop.

for(vector<int>::iterator iter = nums.begin();iter!=nums.end();iter++)
        {
            if(*iter == *(iter+1))
            {
                nums.erase(iter+1);
                iter++
            }

        }

the one within the if statement causes the iter to go out of the scope. there is no need to increment the iter within the if statement.

Edit : Best to mention that erasing the vector invalidates the iterator. so just removing the duplicate incrementation won't be enough. here is a bit more info on this. how to erase from vector in range-based loop?

lastly, this sort of iteration won't be enough to remove duplicate numbers scattered around the vector as such as 0110, 010

edited Oct 01 '18 at 23:19

answered Oct 01 '18 at 22:47

Yucel_K

688
9
17

1

`if(*iter == *(iter+1))` goes undefined at the last element because `*(iter+1)` tries to dereference `end()`; – user4581301 Oct 01 '18 at 22:57
@user4581301 yea noticed that too. but tbh i dont think this code will be sufficient enough to remove dublicates. (0,1,1,0) for exsmple. it needs to be looped twice i believe. – Yucel_K Oct 01 '18 at 23:00
1

Depending on the definition of duplicate, twice won't be enough either: 0,1,1,0 -> 0, 1, 0 . – user4581301 Oct 01 '18 at 23:09

score 1 · Answer 2 · answered Oct 01 '18 at 23:03

An iterator will be invalidated by a call to erase. The erase method returns a new iterator however. The code needs to be careful not to go past the last element with the iter+1 logic. I've fixed up your code below.

I also included a more modern style from here, using remove_if and a set. It avoid some of the iterator confusion. It also works with unsorted vectors. For a very large vector, it appears slower however.

#include <vector>
#include <iostream>
#include <set>

using namespace std;

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
  auto iter = nums.begin();
  while(iter!=nums.end())
  {
      if((!((iter+1) == nums.end())) && 
         (*iter == *(iter+1)))
      {
          iter = nums.erase(iter);
      }
      else
          iter++;
  }
  return nums.size();
}
};

template<typename T>
size_t RemoveDuplicatesKeepOrder(std::vector<T>& vec)
{
    std::set<T> seen;

    auto newEnd = std::remove_if(vec.begin(), vec.end(), [&seen](const T& value)
    {
        if (seen.find(value) != std::end(seen))
            return true;

        seen.insert(value);
        return false;
    });

    vec.erase(newEnd, vec.end());

    return vec.size();
}

int main()
{
  std::vector<int> v{1,1,2,2,3,4,5,5,6,6,6,6};
  Solution s;
  s.removeDuplicates(v);
  for(auto const &element:v)
     std::cout << element << std::endl;
  std::vector<int> v1{1,1,2,2,3,4,5,5,6,6,6,6};
  RemoveDuplicatesKeepOrder(v1);
  for(auto const &element:v1)
     std::cout << element << std::endl;
}

score 0 · Answer 3 · answered Oct 01 '18 at 22:44

You can remove duplicates directly from the console / file input of the test cases without first storing all the values in an array. You can use std::unordered_set<int> to store the values as they are read from cin. Something like this:

std::unordered_set<int>arr;
int test_cases;
cin>>test_cases;
while (test_cases--)
{
    int x;
    cin >> x;
    arr.insert(x);
}

LeetCode remove Duplicates in c++

3 Answers3