@Dave: Sorry my bad. Yes in that case, I cant think of a solution in O(n). I guess your solution of sorting O(nlogn) is the best one in that case.
Thanks, Immanuel On Sat, May 21, 2011 at 2:20 AM, Dave <dave_and_da...@juno.com> wrote: > @Immanuel: It still looks like you are finding the nearest neighbors > of only one point, while the problem was to find the neighbors of > _each_ of the given points. > > Dave > > On May 20, 3:07 pm, immanuel kingston <kingston.imman...@gmail.com> > wrote: > > I guess a <O(nk),O(k)> solution exists. > > > > Have a maxHeap of k elements in our case its 3. > > > > Iterate through the array, compare the (difference between the position > > along a number > > line between ) and the top element of the maxHeap. It it happens to be > > lesser than the top element, pop off the top element and push the current > > element into the maxHeap. Proceeding till the end of the array we will be > > getting the 3 friends of a given person. > > > > Hope I am not wrong. > > > > Thanks, > > Immanuel > > > > > > > > On Thu, May 19, 2011 at 7:33 PM, Dave <dave_and_da...@juno.com> wrote: > > > @Sravanreddy001: You are to find _each_ person's friends. Can you do > > > that in O(n)? > > > > > Dave > > > > > On May 19, 8:59 am, sravanreddy001 <sravanreddy...@gmail.com> wrote: > > > > Also, I think there is no need for sorting the number, its still okey > if > > > the > > > > 3rd person is standing 1st and has the lowest number line value. > > > > > > And, finding the closest 3 number takes, 3*n time.. so.. its O(n) > running > > > > time.. > > > > > > @Dave.. good catch.. :) > > > > > -- > > > 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.- Hide quoted text - > > > > - Show quoted text - > > -- > 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. > > -- 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.
