i think we can use sorting algorithm like insertion sort, in insertion sort whenever we are putting the element into it's proper position we can check whether this elements already exists don't put otherwise insert into into it's proper position (element)
-- Prashant Kulkarni || Lokaha Samastaha Sukhino Bhavanthu || || Sarve Jana Sukhino Bhavanthu || On Wed, May 19, 2010 at 4:09 AM, Aarthi Thangamani < aarthi.thangam...@gmail.com> wrote: > If you are using an extra space to count, why need a heap? An array of size > k can be used to first count the occurances. Then run through the original > array of size N and fill it according to the count our occirances using the > constant k size array. Space O(k) and time O(N) is the best thing I think > of. :( > > > On Tue, May 18, 2010 at 7:11 PM, CHERUVU JAANU REDDY < > jaanu.cher...@gmail.com> wrote: > >> >> Here u r using extra space to store count values.. >> >> >> >> ---------------------------------------- >> CHERUVU JAANU REDDY >> M.Tech in CSIS >> >> >> >> On Tue, May 18, 2010 at 7:01 PM, Jagadish M <jagadis...@gmail.com> wrote: >> >>> >>> On May 18, 8:29 am, Terence <technic....@gmail.com> wrote: >>> > How do you maintain the heap? Could you explain in detail for the >>> > following example: >>> > 1 2 3 3 2 1 1 1 2 3 (n=10, k=3) >>> >>> Basically, in each node we maintain the key and its count. >>> >>> Initially, heap has the first element. >>> 1:1 >>> >>> Search for 2 and insert( since its not found) >>> 1:1 >>> / >>> 2:1 >>> >>> Search for 3 and insert ( since its not found). >>> >>> 1:1 >>> / \ >>> 2:1 3:1 >>> >>> Search for 3; since 3 is already there increment its count by 1. >>> >>> 1:1 >>> / \ >>> 2:1 3:2 >>> >>> Search for 2; since 2 is already there increment its count by 1. >>> >>> 1:1 >>> / \ >>> 2:2 3:2 >>> >>> and so on... >>> >>> >>> Since, there are only k distinct keys the heap size will at most be k; >>> so each search/insert/increment operation takes O(log k) time. >>> >>> >>> Jagadish >>> http://www.cse.iitb.ac.in/~jagadish<http://www.cse.iitb.ac.in/%7Ejagadish> >>> >>> >>> >>> > >>> > On 2010-5-17 22:38, Jagadish M wrote: >>> > >>> > >>> > >>> > > The best algorithm I can think of is to maintain a heap of k >>> elements. >>> > > Takes O(n log k) time. >>> > > Is anything told about the values of the keys? If the keys have >>> values >>> > > less than N, then it is possible to do >>> > > what you say, i.e sort them in place. >>> > >>> > > -Jagadish >>> > >http://www.cse.iitb.ac.in/~jagadish<http://www.cse.iitb.ac.in/%7Ejagadish> >>> > >>> > > On May 13, 7:06 pm, divya<sweetdivya....@gmail.com> wrote: >>> > >>> > >> This problem was asked in google phone interview. We have N element >>> > >> array with k distinct keys(No relation between k& N given so assume >>> > >> k<N) >>> > >> What is the best method to sort this array without using any extra >>> > >> memory? Please elaborate. >>> > >>> > >> -- >>> > >> You received this message because you are subscribed to the Google >>> Groups "Algorithm Geeks" group. >>> > >> To post to this group, send email to algoge...@googlegroups.com. >>> > >> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> > >> For more options, visit this group athttp:// >>> 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 algoge...@googlegroups.com. >>> > To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>> . >>> > For more options, visit this group athttp:// >>> 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 algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
