create a binary search tree by scanning the whole array and if the value already exists increase count field in that node O(nlogn). Now traverse the tree in any order by creating another tree with kery - count. O(nlogn). Doing reverse inorder traversal print value field of each node count number of times O(n).
overall complexity - O(nlogn)+O(nlogn)+O(n) = O(nlogn). On Sat, Sep 3, 2011 at 11:16 PM, Siddhartha Banerjee < [email protected]> wrote: > perhaps we can make it O(mlogm), m= no of distinct elements... just create > a hash table and store the count of the number of time elements occur... > O(n), now sort the m elements and proceed as above... > it is obviously not possible to do it faster than O(mlogm), where m = no of > distinct elements... > so order = O(n+mlogm)=O(mlogm)(???, assuming m!<<n) > > -- > 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. > -- ........................ *MOHIT VERMA* -- 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.
