Author |
Topic: removing duplicates from unsorted array in O(n) (Read 7041 times) |
|
mcprabhakaran
Junior Member
Posts: 62
|
 |
removing duplicates from unsorted array in O(n)
« on: May 22nd, 2007, 9:12pm » |
 Quote  Modify
|
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??
|
|
 IP Logged |
|
|
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender: 
Posts: 236
|
|
Re: removing duplicates from unsorted array in O(n
« Reply #1 on: May 22nd, 2007, 11:05pm » |
Quote Modify
|
on May 22nd, 2007, 9:12pm, 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
|
|
IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
mcprabhakaran
Junior Member
Posts: 62
|
|
Re: removing duplicates from unsorted array in O(n
« Reply #2 on: May 23rd, 2007, 12:12am » |
Quote Modify
|
Fine ... Thanks
|
|
IP Logged |
|
|
|
brute_force
Newbie
Posts: 5
|
|
Re: removing duplicates from unsorted array in O(n
« Reply #3 on: Jun 16th, 2007, 1:01am » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: removing duplicates from unsorted array in O(n
« Reply #4 on: Jun 16th, 2007, 5:24am » |
Quote Modify
|
on Jun 16th, 2007, 1:01am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
brute_force
Newbie
Posts: 5
|
|
Re: removing duplicates from unsorted array in O(n
« Reply #5 on: Jun 16th, 2007, 6:58am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: removing duplicates from unsorted array in O(n
« Reply #6 on: Jun 16th, 2007, 7:38am » |
Quote Modify
|
on Jun 16th, 2007, 6:58am, 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(n2); 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.
|
| « Last Edit: Jun 16th, 2007, 7:40am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
aki_scorpion
Newbie
Gender:
Posts: 13
|
|
Re: removing duplicates from unsorted array in O(n
« Reply #7 on: Jul 9th, 2007, 1:28am » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: removing duplicates from unsorted array in O(n
« Reply #8 on: Jul 9th, 2007, 2:43am » |
Quote Modify
|
on Jul 9th, 2007, 1:28am, 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).
|
| « Last Edit: Jul 9th, 2007, 2:43am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
BM
Newbie
Posts: 1
|
|
Re: removing duplicates from unsorted array in O(n
« Reply #9 on: Aug 30th, 2007, 11:08am » |
Quote Modify
|
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 ..
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: removing duplicates from unsorted array in O(n
« Reply #10 on: Aug 30th, 2007, 11:15am » |
Quote Modify
|
on Aug 30th, 2007, 11:08am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print