Finding duplicates in a multiset is a pretty standard problem. I've only ever heard of two solutions, and it's unlikely there are others.
One is to sort, which will place duplicates adjacent to each other, so you can find them by comparing a[i] with a[i+i] for all I. This algorithm is O(sorting time + scanning time), so O(n log n) using comparison sort, O(n) for counting sort, and O(n log k) for radix sort where k is magnitude of max element. Storage is O(1), O(k), and O(log k) respectively. The other is to use a set data structure, scan the input checking to see if the current element is already in the set (if so, it's a duplicate) and and then adding that element. This one is O(scanning time + n * lookup time + n * insert time). The most efficient set type is data dependent. For dense small integers, it's a bitmap. For arbitrary comparable keys it's either hash table or balanced tree depending on key type. Note that here the set insert and lookup depend not on n but on the number of _unique_ keys. If you have many repeats (think of a million 3's and 10 other numbers), this can have an impact. If you limit yourself to O(1) space, an in-place comparison sort and check of adjacent elements seems the best you can do: O(n log n). And the original data order is destroyed. If you must also maintain data order, O(n^2) all pairs comparison seems the best you can do. On Nov 24, 1:02 am, kumar raja <rajkumar.cs...@gmail.com> wrote: > In the given array all the elements occur single time except one element > which occurs 2 times find it in O(n) time and O(1) space. > > e.g. 2 3 4 9 3 7 > > output :3 > > If such a solution exist can we extend the logic to find "All the repeated > elements in an array in O(n) time and O(1) space" > > -- > Regards > Kumar Raja > M.Tech(SIT) > IIT Kharagpur, > 10it60...@iitkgp.ac.in -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
