[algogeeks] Discussion on unique-elements-in-an-array
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 to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Discussion on unique-elements-in-an-array
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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Discussion on unique-elements-in-an-array
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. 2.2 xroot : set x as left son of root. 2.3 else : set x as right son of root. 3. continue with all other elements of array and insert them into a bst. and while inserting them check if that no. is already present in the bst.(by discarding the no. in case it matches with any node of bst and moving to next element of array) this i think can solve the problem in O(n*lgn) -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Discussion on unique-elements-in-an-array
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 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Discussion on unique-elements-in-an-array
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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Discussion on unique-elements-in-an-array
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 Chapter 7 : heap Sort. --~--~-~--~~~---~--~~ 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 options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Discussion on unique-elements-in-an-array
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 elements
only.
Only restriction is the memory.
--~--~-~--~~~---~--~~
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 options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Discussion on unique-elements-in-an-array
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 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 options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Discussion on unique-elements-in-an-array
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 options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Discussion on unique-elements-in-an-array
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 PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
