the link is not being sorted the elemnts are being read frm the array and inserted at the end of the list ( not sorting ). while traversing to end of the list jst chk if the element is already present in the list
On 8/16/06, Vishal <[EMAIL PROTECTED]> wrote: > The simple way would be (for random numbers scenario) to sort the array - > O(n log n) - and then traverse through the array to find the repeated > element - O(n). > The creation of link list is nothing but insertion sort, which is O(n^2). > > ~Vishal > > > On 8/15/06, akshay ranjan <[EMAIL PROTECTED]> wrote: > > > > Not sure About the soln. but here goes > > > > Create a link list > > The node contains the number along with the list pointer. while > > creating the list impose a condition on insertion to chk for > > repetion.. i.e while traversing the list chk if the element is already > > inserted or not .given that n-1 are unique numbers and 1 no. repeats > > only , each elt will keep on being insertwed at end of the list while > > at the repeated element u could print the element and exit > > > > On 8/16/06, Lego Haryanto < [EMAIL PROTECTED]> wrote: > > > > > > Not sure about the line O(k * n) = O(n) ... > > > > > > That's probably assuming the hash-table doesn't have collision, which > pretty > > > much is O(1). What if somehow the numbers are chosen so that a > particular > > > hashtable would endure so many collisions, ... the complexity can then > be > > > worst-case O(n^2) ... > > > > > > > > > > > > On 8/15/06, ridvansg <[EMAIL PROTECTED]> wrote: > > > > > > > > Hi, here is the solution. > > > > 1. Create a hashtable . > > > > 2. Go through the numbers inserting each into the hashtable. When > > > > insert the number check if it already exists, if so - this is the > > > > repeating number. > > > > > > > > The complexity: O(k*n) = O(n) > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > -- > > > Fear of the LORD is the beginning of knowledge (Proverbs 1:7) > > > > > > > > > > > > > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
