Thread: Really basic remove duplicates from array

  1. #1
    Registered User
    Join Date
    Aug 2002
    Posts
    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
    Last edited by Chris Fowler; 08-09-2002 at 08:22 PM.

  2. #2
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    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. #3
    *ClownPimp*
    Guest
    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. #4
    *ClownPimp*
    Guest
    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. #5
    *ClownPimp*
    Guest
    this board doesnt like me today...

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

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    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
    My best code is written with the delete key.

  7. #7
    Registered User
    Join Date
    Jan 2002
    Posts
    552
    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?!?!
    C Code. C Code Run. Run Code Run... Please!

    "Love is like a blackhole, you fall into it... then you get ripped apart"

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >good lord prelude, this is a really old thread
    Serves me right for linking directly to the thread from Who's Online.

    -Prelude
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 02:02 PM
  2. Basic array segmentation fault
    By Argentius in forum C++ Programming
    Replies: 2
    Last Post: 11-03-2007, 04:50 AM
  3. Modify an single passed array element
    By swgh in forum C Programming
    Replies: 3
    Last Post: 08-04-2007, 08:58 AM
  4. Type and nontype parameters w/overloading
    By Mr_LJ in forum C++ Programming
    Replies: 3
    Last Post: 01-02-2004, 01:01 AM
  5. Help with an Array
    By omalleys in forum C Programming
    Replies: 1
    Last Post: 07-01-2002, 08:31 AM