can you please elaborate nature of inputs??
are they partially sorted or may be random.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email
what is the range of numbers.if the array has numbers between 1 to n
then there can be o(n) solution.
Regards
Priyaranjan
http://code-forum.blogspot.com/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
i think this could be done if we use binary search tree for finding
the duplicates.
1. take first element in the array as the root.
2. for the next input element(say x) there can be 3 cases:
2.1 x==root : since this is a duplicate we discard this element
and move to next no. in the list.
You can refer the following algorithm
Let the elements be in the form of an array A[1...N]
1. Sort all the elements of A(This can take at least O(n) time).
2. For i=1 to N, do:
while( ( i+1 = N) AND (A[i] == A[i+1]) )
remove A[i+1].
3. END
--
You received this message because you
Remove elements from array and insert into a hash table, ignoring
duplicates. O(n).
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
Heap sort has a function heapify which will build the heap. If you
just modify this heapify algorithm to eliminate the repeated elemenst
it will work in O(nLogn).
Also this will work for any number of repeated elements. you can find
this algo in hte Design analysis and algorithms by Corment in
There can be multiple ways to do this.. obviously sorting gives you
o(nlogn).
another approach of hashtable gives o(n)
and here is another approach:
1. maintaining array of size N, initialized to 0. Say B
2. for(i=0;iN;i++) { B[a[i]]++;}
3. Output all values with B[i] = 1 , which gives unique
You can use a tweak of Merge Sort:
Only change while merging of the two lists:
Just while merging if two elements are equal you can make one of them
equal to some predefined value.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to
bitmap
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more
using hash table
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL
10 matches
Mail list logo