@above sort the array using any inplace algorithm and then chk adjacent for duplicates... this seems to me only inplace solution for chking duplicates
On Sat, Jul 3, 2010 at 5:57 PM, Vikas Jayaprakash < [email protected]> wrote: > I dint understand answer to rotation question. > > Also is there any way of identifying duplicates in an array without using > any extra memory (like creating hash table takes extra memory). > > Any reference w.r.t book (or google book) to seek the concept behind two > questions? > > Please let me know. > > Regards, > Vikas J > > > On Sat, Jul 3, 2010 at 12:47 PM, Abhirup Ghosh <[email protected]>wrote: > >> How can you find smallest element in the array in O(logn) time? Can >> you please elaborate? >> >> -Abhirup >> >> >> >> On Fri, Jul 2, 2010 at 3:44 PM, jalaj jaiswal <[email protected]> >> wrote: >> > 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]<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. >> >> > > > -- > Thanks & Regards, > Vikas Jayaprakash > > -- > 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.
