In hash map insertion and seach take O(logn) time but less space. So according to sharad insert all elements in hash map which will take O(nlogn) time and 0(n) space.
But if you are sure about the range of numbers which would appear in the list, you can use counting mechanism. Like if you know number will be 1 - 1000. Then have an array of size 1000. So space complexity will be O(k) ( k = largest number ) and time complexity for all insertion would be O(n) and time complexity for generating 3 arrays by checking each element would be O(k) space = O(k) time = O(n+k) On Sun, Oct 3, 2010 at 11:22 AM, sharad kumar <[email protected]>wrote: > it will take same amount of memory na....key value is element and vaule is > the amount of times element occurs..... > > > On Sun, Oct 3, 2010 at 11:11 AM, mac adobe <[email protected]> wrote: > >> i think hash map takes lots of memory ... please correct me if i am wrong >> here .. >> >> anyways its a soluton but i would like to have a different solution .. :) >> >> --mac >> >> >> On Sun, Oct 3, 2010 at 10:55 AM, sharad kumar <[email protected]>wrote: >> >>> cant u use a hash map buddy??? >>> >>> On Sun, Oct 3, 2010 at 10:35 AM, mac adobe <[email protected]>wrote: >>> >>>> You are given a very long array of integers . Some number in this >>>> integer array come 1 time , some 2 times some 3 times . create 3 different >>>> arrays . >>>> Array 1 will have numbers with numbers comming only1 time , Array 2 will >>>> have numbers with numbers comming 2 times, Array 3 will have numbers with >>>> numbers repearting 3 times , >>>> >>>> >>>> Can you extend the solution to create array_x with elements repeating x >>>> times ? >>>> >>>> thanks >>>> --mac >>>> >>>> -- >>>> 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. >>>> >>> >>> >>> >>> -- >>> yezhu malai vaasa venkataramana Govinda Govinda >>> >>> -- >>> 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. >> > > > > -- > yezhu malai vaasa venkataramana Govinda Govinda > > -- > 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, Gaurav Gupta Associate Software Engineer IBM Software Lab |India Email: [email protected] Ph No. : +91-7676-999-350 "Quality is never an accident. It is always result of intelligent effort" - John Ruskin -- 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.
