We can build a wrapper object having two fields one th actual integer in the array and the count o the integer in the given array. Then build an array of those objects. Range of this array can be found easily by finding max and min of the array in O(n) time. We can build the auxiliary array in O(n) time. Then we can sort that array on the basis of count field using counting sort in O(n). As counting sort is stable sort if two counts are equal then the sequence is maintained. So the whole process is done in O(n). But the space complexity is O(n) as two auxiliary arrays are needed.
-Abhirup On Sun, Jul 4, 2010 at 3:20 AM, Amir hossein Shahriari <amir.hossein.shahri...@gmail.com> wrote: > we can apply that case in the comparator or sort them after counting again > in nlogn (with respect to number of occurrences and their first index) > since the first occurrence of a number happens when it's not inserted in bst > we can do this easily > > -- > 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. > -- 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.
