I am trying one of the practice problems on hackerrank.
I'm aware there is a better way to do it, but I would like to know why this way didn't work to understand it better.
The vector erase function seems to work as intended until the last couple of times and then erases at the wrong index, even though nothing changes.

debugger output:
1, 1, 3, 1, 2, 1, 3, 3, 3, 3, //what is currently in the vector
Delete indx 0 & 1 //The first pair that I will erase and increment count

3, 1, 2, 1, 3, 3, 3, 3, //continue...
Delete indx 0 & 4

1, 2, 1, 3, 3, 3,
Delete indx 0 & 2

2, 3, 3, 3,
Delete indx 1 & 2 //says to delete the first and second three

3, 3, //it looks like the 0th and some other index was erased instead
Delete indx 0 & 1

count returned is: 5
let me know if I can add to this question to make it better, thanks

int i, count = 0;

for (i=0;i<ar.size()-1;i++)
{
    for (int j=i+1;j<ar.size();j++)
    {
        if (ar[i] == ar[j])
        {
            ar.erase(ar.begin()+i-1);
            ar.erase(ar.begin()+j-1);
            count++;
            i=-1;
            break;
        }
    }
    if (ar.size()== 0)
        break;
}

1 Answers

0
Daniel On

From what I understood, you only need the count of pairs (considering the removals).

for(int i = 0; i < ar.size() - 1; i++){
    for(int j = i + 1; j < ar.size(); j++){
        if(ar[i] == ar[j]) {
            ar.erase( ar.begin() + j );
            count++; 
            break;
        }
    }
}

This way you only need to perform 1 call of erase (which is slow, considering it moves all the elements in the right of the deleted element 1 slot to the left).

If you have big vectors, also consider not using ar.size() all the time (at least in j loop, since in i loop it's kind of essential). Try for(int j = i + 1, len = ar.size(); j < len; j++).