wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> removing duplicates from unsorted array in O(n)
        
(Message started by: mcprabhakaran on May 22^nd, 2007, 9:12pm)

Title: removing duplicates from unsorted array in O(n)
Post by mcprabhakaran on May 22^nd, 2007, 9:12pm

HI,

How to remove duplicates from unsorted array in O(n). ??

If we sort the array using quick sort then we can remove dups easily. Hope this is in O(n). Is this Ok??

Title: Re: removing duplicates from unsorted array in O(n
Post by R0B1N on May 22^nd, 2007, 11:05pm

on 05/22/07 at 21:12:40, mcprabhakaran wrote:

HI,

How to remove duplicates from unsorted array in O(n). ??

If we sort the array using quick sort then we can remove dups easily. Hope this is in O(n). Is this Ok??

Quick Sort is O(nlogn) and O(n^2) in the worst case

if we are allowed to use O(n) extra space , then You can maintain a Hash table of Seen Objects

Title: Re: removing duplicates from unsorted array in O(n
Post by mcprabhakaran on May 23^rd, 2007, 12:12am

Fine ... Thanks

Title: Re: removing duplicates from unsorted array in O(n
Post by brute_force on Jun 16^th, 2007, 1:01am

Whats the range of nos in the array here?
Note:Hash table can be used only if numbers in array are in the range O(n).

Title: Re: removing duplicates from unsorted array in O(n
Post by towr on Jun 16^th, 2007, 5:24am

on 06/16/07 at 01:01:16, brute_force wrote:

Whats the range of nos in the array here?
Note:Hash table can be used only if numbers in array are in the range O(n).

That's not true. A hash table can be used for any range. I think you are confusing it with a (normal) look-up table.

Title: Re: removing duplicates from unsorted array in O(n
Post by brute_force on Jun 16^th, 2007, 6:58am

What I meant was initialising hash table has to be O(n).

Could you plz explain your algorithm?
How do you use hash table if the range is -infinity to +infinity.
Will the algorithm work in general(ex:range is 0 to n^n).Algo should not assume anything like collisions will be negligible etc

Title: Re: removing duplicates from unsorted array in O(n
Post by towr on Jun 16^th, 2007, 7:38am

on 06/16/07 at 06:58:35, brute_force wrote:

What I meant was initialising hash table has to be O(n).

Well, if n is the total number of unique elements (or in the same order at least), then I suppose that's correct.

Quote:

How do you use hash table if the range is -infinity to +infinity.

It hashes the elements to fit a smaller range.

Quote:

Will the algorithm work in general(ex:range is 0 to n^n).

It would work for any range. Any type of data element too, as long as you have a way of hashing it properly. (Finding a good hashing function is a bit of an art, but luckily there's libraries for it in nearly every programming language)

Quote:

Algo should not assume anything like collisions will be negligible etc

If you only look at worst case behaviour, than no, it shouldn't.
But then, as mentioned before, in the worst case quicksort is O(n²); in practice though, it is virtually always faster than mergesort (which is O(n log n)). Which is why quicksort is practically always used when sorting an array is called for.
The practical behaviour of algorithms is worth considering. In practice a decent implementation of a hash-table has O(1) insertion and O(1) retrieval time.

Title: Re: removing duplicates from unsorted array in O(n
Post by aki_scorpion on Jul 9^th, 2007, 1:28am

Hi

Can we use a Map to solve such a problem ?(Map is a type of associative array). We just increment the value of the corresponding part.
Eg.
Say the array a=[1,2,4,4,2];
then make a map M
if (M[a[i]==NULL)
M[a[i]=1;
else
M[a[i]++;
----------------------------------
Later it can be read using an iterator

-----------------
Could some one tell me the run time for a Map in such an example ?
Else the run time seems to be O(n).

Title: Re: removing duplicates from unsorted array in O(n
Post by towr on Jul 9^th, 2007, 2:43am

on 07/09/07 at 01:28:09, aki_scorpion wrote:

Could some one tell me the run time for a Map in such an example ?

A map has O(log n) for accessing if it's implemented well. You have to search for the key, after all.
So multplying that in gives O(n log n).

Title: Re: removing duplicates from unsorted array in O(n
Post by BM on Aug 30^th, 2007, 11:08am

but what if we are not allowed to use that O(n) extra space as well..??? is it possible to find out the duplicates and remove those .. ???

Title: Re: removing duplicates from unsorted array in O(n
Post by towr on Aug 30^th, 2007, 11:15am

on 08/30/07 at 11:08:58, BM wrote:

but what if we are not allowed to use that O(n) extra space as well..??? is it possible to find out the duplicates and remove those .. ???

In some case, if you can use radix sort or a similar O(n) sorting method.
In the general case, I don't think you can have both O(n) time and O(1) space complexity; one's gotta give.