The worst case for any sort is *"nlogn"* . have 2 see some other approach than sorting [?]
*Subhransu Panigrahi * *Mobile:* *+91-9840931538* *Email:* subhransu.panigr...@gmail.com On Fri, Apr 1, 2011 at 6:02 PM, snehal jain <learner....@gmail.com> wrote: > For a set S of n real numbers, a pair of elements x, y belong to S, > where x < y, are said to be close if > y – x <= ( max(S) – min(S) ) / (n-1) > Suppose you are given an unsorted array A[1 : n] of distinct real > numbers. Design an algorithm that finds a pair of close numbers in A > in O(n) time. > > my solutions > > 1. brute force: complexity n2 > 2. sort the array. > take 2 ptrspt1 and pt2.initially pt1 points to 1st elementand pt2 pts > to 2nd element. check if they are close nos. > > case1; if they r closeincrement pt2. and again check. repeat this > until u find close pairs. when pt1and pt2 doesnt pt to close pairat > this point all elements b/w pt1 and pt2 are also close. increment > close_pair_count accordingly, check if element jst b4 pt2 and at pt2 > are also close. > > case 2: increment both pt1and pt2 and continue > > repeat above steps til u reach end of array.. > > m unable to think linear algo.please help.. > > -- > 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.
<<323.gif>>
