second question can be done in O(logn) do a modified binary search to find the starting index of the rotated array i.e the smallest element.
after that you have two sorted arrays.. for eg 789 1236 (your modified binary search should return index of 1) now check if the elemnent you are searching in greater then a[min] then do binary search in 1st array else do in second array On Fri, Jul 2, 2010 at 3:29 PM, Abhirup Ghosh <[email protected]> wrote: > 1. (1) Maintain a hash table and insert the elements in the table when > passing through the array. And if there is a collision then that > element is a duplicate element in the array.Time - O(n) and the space > is O(n). > (2) Duplicate is detected by the above process. Then it can be easily > removed. I can't get what it means that remove duplicates without > hampering the array! The hash table anyway would contain all the > distinct elements. > > 2. Pass the array checking if the current element is lower than the > previous one. If found such element The current element is the start > of the original sorted array. If such element is not found then the > first element of the present is the desired element. Note down the > index. Takes O(n). > > Now do binary search. The mid point of the array is manipulated by > considering the index that we have saved. One trivial method could be > keep track of the array in each recursion and then get the half length > and then calculate the index according to the placement of the > starting index at that recursion. This takes O(logn). > > So overall Time O(n). Space O(1) [no extra space]. > > > Correct me if I am wrong. > > -Abhirup > > > > > On Fri, Jul 2, 2010 at 1:50 AM, Vikas Jayaprakash > <[email protected]> wrote: > > Hi AlgoGeeks, > > Can anyone provide me answers for the below. > > > > 1. given an array of random integers write a program to (1) detect > > duplicate (2) remove duplicate (array should not get hampered at any > > cost!). > > 2 - In a sorted array some of the elements say N are rotated. for > > example initially 1 2 3 6 7 8 9 after rotation of 3 elements 7 8 9 1 2 > > 3 6.So how do you search an element in this array? > > > > > > Regards, > > Vikas J > > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > > [email protected]<algogeeks%[email protected]> > . > > For more options, visit this group at > > http://groups.google.com/group/algogeeks?hl=en. > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
