@Varun: Here is an algorithm using sorting only:
1. Append an index onto each number, so your example becomes {{4,0}, {3,1},
{2,2}, etc.}
2. Sort the numbers and their associated indices into ascending order by
number. Your example becomes {{2,2}, {2,6}, {3,1}, {4,0}, {4,4}, etc.}. If
the sort is not stable, the indices on equal numbers may not be in order,
as I've shown here, but that doesn't matter. It will be taken care of in
the next step.
3. Scan the array, and collapse every sequence of adjacent entries with
equal numbers into one entry with the lowest index, and append the
frequency to the entry. Your example becomes {{2,2,2}, {3,1,1}, {4,0,2},
etc.}
4. Sort the array with frequency as the primary key and index as the
secondary key. You get {{4,0,2}, {2,2,2}, {6,5,2}, {3,1,1}, {5,1,3}}.
5. Reexpand the array by repeating each number according to its frequency,
giving {4,4,2,2,6,6,3,5}.
Dave
On Wednesday, February 1, 2012 2:58:43 AM UTC-6, Varun 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 unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
