Build a hashmap with the array value as a key mapping to a struct which contains the key, frequency, and location of first occurance. Then sort the hashed elements comparing first by frequency and breaking ties based on first occurance. Then iterate through the sorted elements and fill in the array. All steps are O(n) except for the sort, so the overall complexity is O(n*log n). Don
On Feb 1, 2:58 am, Varun <[email protected]> wrote: > I was asked this question sometime during an interview. > > WE have an array of known length. The elements in array can be repetitive. > now sort the array based on frequency of occurrence of each element in > array. > Eg: a= {4.3.2.5.4.6.2.6} > after sorting a={4,4,2,2,6,6,3,5} > > 4,2,6 all occurs twice, in this case retain the order in which they > appeared in original array. > I was able to give a solution using hashing the elements of the array to a > new array, and if hash matches, incrementing the count, and then sort the > hash values. Later, re scan the array to retain the order in case there's a > match in frequency of any two element. > > Looking for better alternatives. > Please pour in. -- 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.
