January 11th, 2014, 09:21 AM
Print values of array by popularity
Given an array with integer values in the range [0, 100], print the values by popularity.
array: 60, 60, 70, 80, 80, 80, 80, 100;
output: 80 80 80 60 60 70 100.
complexity restriction: should be linear.
cant use advance data structure like lists or hashmaps,
to build counter array of buckets of size 101, and count each value.
then i need to sort the counter array(its still linear), but how i can keep track that the value of 80 appeared 3 time?
I mean i need to sort the values of the counter with the indexes as well.
Thanks in advance
January 11th, 2014, 10:38 AM
Use a hashmap. Then go through the array one element at a time and look for it in the hashmap. If the value doesn't already exist in the hash map, then insert it in with a count of 1. If the value already exists, then increment the count. Finally, sort the hash map in reverse order of the count and then display it. Easy!
Up the Irons
What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
"Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
Down with Sharon Osbourne
"I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
January 11th, 2014, 10:43 AM
my fault i didnt mention is but cant use hasmap, only arrays, no lists or more advance data structure
Originally Posted by Scorpions4ever
January 11th, 2014, 01:49 PM