calculating frequency of a number in an Array

Question

I have an array, scores[5][5] and it is filled with test scores.

I need to find the most frequently occurring score and return it.

Answer 1

Well, there's 2 parts: iterating the scores and storing the frequency of each score. Both of them involve using an array/arraylist. We can direct questions if you want more help. :D

Answer 2

I would simply create a HashMap<Integer,Integer> where the first integer is the value in the scores array and the second is the frequency.

Then process the array filling in the hashmap. If a key already existed, up the count by one. If it's a new key, set it to one.

Then process the hashmap to find the value with the largest occurrence.

---

I was going to work on the source code once I got access to a machine where Java was installed but, since it's now marked homework, it's algorithms only (which will be better for you in the long run anyway):

Create empty hashmap freq
For each entry in your array (probably nested loops):
    If entry.value is not in freq:
        Add entry.value to freq, set its count to zero
    Increase count of freq.value
Set max_count to 0
For each item in freq:
    If item.count is greater than max_count:
        Set max_list to an empty list
        Set max_count to item.count
    If item.count is equal to max_count:
        Append item.value to max_list
If max_count is greater than 0:
    Output max_count, max_list

That's the basic algorithm I would follow which consists of two sequential loops.

The first simply creates a mapping of values to counts so that you can find the greatest count later.

The second runs through the map and creates a list of the values with the highest count.

Answer 3

Since scores are likely to be in a bounded range (e.g. 0..100), you can use a counting array to do this quickly. Basically, you're doing the first phase of counting sort.

The count for all possible scores starts at 0, then for each score s, increment count[s]. Once all scores are processed, scan the count and see which count[k] is the highest.

You can also keep track of the most frequent score as you're doing the counting. Just do something like this:

// init
mostFrequent = 0;

// during increment
count[s]++;
if (count[s] > count[mostFrequent]) {
  mostFrequent = s;
}

Since your scores are arranged in a 2d matrix (for some reason?), you can process each score as follows:

int[] count = new int[RANGE]; // valid scores are 0..RANGE-1

mostFrequent = 0;
for (int[] tuplet : scores) {
   for (int s : tuplet) {
     count[s]++;
     if (count[s] > count[mostFrequent]) {
        mostFrequent = s;
     }
   }
}

report(mostFrequent, count[mostFrequent]);

Answer 4

Or keep a pointer to the the current largest one as you go. Each time you create or update, compare to see if you've just exceeded the previous largest and replace it if you have. Saves another pass through the hashmap.

Answer 5

For things like this, write code that models how you would do things in real-life.

Let's model:

Your [5][5] array: It's just a grid of numbers with 5 columns and 5 rows.

Start at the 0,0 position - read the value at that position, and start a list (in Java, an ArrayList or HashMap), add the number to the list and give it a hash mark (value of 1), to indicate you've seen it once.

Go across the row and then back left and down a row, et al.

Each number you read, check if it's already on your list. If it is, just make another hash mark (add 1). If not, then add the number to your list and give it a hash mark.

After you finish reading the array, look at your list, from the beginning, and keep track of the number with the most hash marks you've seen by putting your finger on it (storing the number in a variable).

Return that last variable.