Fatest way to remove duplicate elements from a sorted array ?

Question

Input: {5, 8, 5, 3, 3, 2, 7}
Output: {5, 8, 3, 2, 7, ?, ?}

Idea is that we should remove the duplicate number from the array and should return the array in the original form (obviously without duplicate).

Please help me with an efficient algorithm or C code.

Answer 1

It can be done in O(n)

void dedup(vector<int> &v)
{
    int i = 0;
    for(int j = 1; j < v.size(); ++j)
    {
        if(i != j)
        {
            if(v[i] != v[j])
            {
                v[++i] = v[j];
            }
        }
    }

    v.resize(i+1);
}