#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    2
    Rep Power
    0

    Print values of array by popularity


    Hello everyone.

    Given an array with integer values in the range [0, 100], print the values by popularity.

    example:
    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,
    only arrays.
    my idea:
    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
  2. #2
  3. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,640
    Rep Power
    4247
    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
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2014
    Posts
    2
    Rep Power
    0
    Originally Posted by Scorpions4ever
    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!
    my fault i didnt mention is but cant use hasmap, only arrays, no lists or more advance data structure
  6. #4
  7. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,392
    Rep Power
    1871
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper

IMN logo majestic logo threadwatch logo seochat tools logo