# Thread: Really basic remove duplicates from array

1. ## Really basic remove duplicates from array

Sorry guys but anyone know a good quick algorithm for removing duplicates from an array, I've lost all my old books and alas without a template. My current ver isn't working all that well.

Would love to hear from you guys on a possible solution.

--Duh discovered the search function of the site and answered my question, but if anyone wants to submit some help here I'd gladly take their advice.

Thank you
Chris

2. You can sort the array in O(n lg n) and then remove
duplicates by replacing them with a invalid entry in O(n). You could insert n items into a tree structure in a bit more than
O(n lg n) depending on what kind of tree you use. You could insert them into a hash table, when the entry is already in the hash table it's a duplicate. This is O(n) if each insertion into
the hash table is O(1).

3. void duprem(int *arr, int size)
{
bool table[256] = {false};
int i = 0, j = 0;

while (j < size) {
if (!table[arr[j]]) {
arr[i++] = arr[j];
table[arr[j]] = true;
}
++j;
}
}

O(n)

4. the board should make sure your pass is correct before assuming your not registered...

Code:
```void duprem(int *arr, int size)
{
bool table[256] = {false};
int i = 0, j = 0;

while (j < size) {
if (!table[arr[j]]) {
arr[i++] = arr[j];
table[arr[j]] = true;
}
++j;
}
}

O(n)```

5. this board doesnt like me today...

'int *arr' should be 'char *arr'

6. Assuming that this isn't homework that requires you to hand code the algorithm the best way would be to make use of the <algorithm> header:
Code:
```#include <iostream>
#include <algorithm>

const int SIZE = 21;

int main()
{
int vals[SIZE] = {1,2,3,5,6,8,3,7,9,0,6,5,7,5,3,5,7,5,2,4};

std::sort ( vals, vals + SIZE );
int *end = std::unique ( vals, vals + SIZE );

for ( int *it = vals; it != end; it++ )
std::cout<< *it <<' ';

std::cout<<std::endl;
}```
-Prelude

7. good lord prelude, this is a really old thread (i was thinking someone was trying to steal my nick).

on another subject, where did I get off thinking he was using an array of chars?!?!

8. >good lord prelude, this is a really old thread
Serves me right for linking directly to the thread from Who's Online.

-Prelude