Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# help with counting occurrences of elements in an array

Dan Rana
Greenhorn
Posts: 20
i'm trying to read through an array and count the number of times each number is found in the array and print the results in a table.
ex: the array contains: 4 ,3 ,2 ,1
the output:
Number Iterations
3 1
2 1

the number "1" and how many times it shows up isn't displayed and I can't figure it out.
this only happens when the last number shows up only once.

*note: i wanted to exclude the 4, that's why i set holder = array[1]

Junilu Lacar
Bartender
Posts: 7771
62
• 1
I'm going to try to help you work through the problem, Dan, rather than give you my solution for it. I encourage other folks to follow my lead and refrain from giving your answer if you have already worked through it yourself. It will be more beneficial to Dan in the long run.

First, it helps if you try to talk through the steps of the algorithm.

For example, if I were doing a binary search algorithm, I would try to talk through the strategy like so:

Given a list of numbers and a number that I need to look for within that list, using the binary search algorithm, I would do the following:
1. Make sure the list is sorted in ascending order
2. If the list has only one element, then I'm done. If the element is what I'm looking for, the search succeeded, otherwise the number I'm looking for is not in the list.
3. Go to the middle element of the list. This becomes the current element.
4. If the current element is the one I'm looking for, then I'm done.
5. If the current element is greater than what I'm looking for, go back to step 2 but use a new list that's made up of only the elements before the current one.
6. If the current element is less than what I'm looking for, go back to step 2 but use a new list that's made up of only the elements after the current one.

Now, try doing something like the above for your problem then we can go from there. Let me start it for you:

Given a list of numbers, I would like to see what numbers are in the list and how many times each occurs in the list. To do this, I would:
1. ... (you fill this in)

Just out of curiosity, why are you purposely excluding the first element?

Dan Rana
Greenhorn
Posts: 20
Junilu Lacar wrote:
Given a list of numbers, I would like to see what numbers are in the list and how many times each occurs in the list. To do this, I would:
1. ... (you fill this in)

1. take the first number and check the others to see if they equal that number. if i run into one that equals the first number, i add that to the count.
2. once I'm done searching the numbers, i take the second number and search the rest to see if any of them are equal to it.
3. i do this until after i reach the last number and search the list for it.

Junilu Lacar
Bartender
Posts: 7771
62
• 1
Dan Rana wrote:
1. take the first number and check the others to see if they equal that number. if i run into one that equals the first number, i add that to the count.
2. once I'm done searching the numbers, i take the second number and search the rest to see if any of them are equal to it.
3. i do this until after i reach the last number and search the list for it.

Ok, that's a good start. Let's try to make it better. One thing with this approach is that you're going through the list multiple times. You can tweak your approach a little so that you only go through the list one time. Imagine you had a box of different colored balls. There could be any number of balls for each color. How would you go through the box of balls so that you only touched each ball exactly once throughout the whole process, keeping a tally of it's color and how many balls you've pulled out that are the same color? This is the same approach you need to take here. Go ahead, give it a shot. It's getting kind of late for me here in the US Midwest so I'm going to leave it at this for now and I'll check back with you again in the morning.

Dan Rana
Greenhorn
Posts: 20
Junilu Lacar wrote:
Ok, that's a good start. Let's try to make it better. One thing with this approach is that you're going through the list multiple times. You can tweak your approach a little so that you only go through the list one time. Imagine you had a box of different colored balls. There could be any number of balls for each color. How would you go through the box of balls so that you only touched each ball exactly once throughout the whole process, keeping a tally of it's color and how many balls you've pulled out that are the same color? This is the same approach you need to take here. Go ahead, give it a shot. It's getting kind of late for me here in the US Midwest so I'm going to leave it at this for now and I'll check back with you again in the morning.

1.grab a ball of a certain color, take it out, add it to the count of its color.
2. grab another, if it's not the same color, add it to a different count for that color
3. do this until the box is empty.

Winston Gutkowski
Bartender
Posts: 10527
64
Dan Rana wrote:1.grab a ball of a certain color, take it out

And how would you know which colour to grab?

Remember Junilu's advice: Ideally, you want to "go through the box of balls so that you only touched each ball exactly once throughout the whole process".

add it to the count of its color

And how would you keep that? Particularly if you need to keep counts of more than one colour. (Hint: have a look at the HashMap class)

do this until the box is empty

OK, so now it sounds like you want to count all the colours in your box, not just one. Oddly enough, that actually makes the problem easier.

Winston

Junilu Lacar
Bartender
Posts: 7771
62
Hi Winston! Glad you joined in on the fun

Winston's right, Dan, you could look at HashMap for an idea. Or if you want to keep it abstract for now, think about rewording "add it to the count of its color" -- think real world for now, no other software except your brain. Yes, I know you're probably itching to get down to coding it up already but just bear with me a little bit more. You're almost there.

So, what would you do with those balls as you take them out of the box? Do you just drop them on the floor? Where are you noting down all these different counts? In your head? Pretend you have really bad memory and forget easily, so you don't want to track the counts in your head. Pretend for just a minute that you didn't have a pen and paper handy either. Then, pretend that aside from the box with all the colored balls in it, there's a bunch of other empty boxes sitting off to the corner. How would you refine your strategy now?

Dan Rana
Greenhorn
Posts: 20
Junilu Lacar wrote:
So, what would you do with those balls as you take them out of the box? Do you just drop them on the floor? Where are you noting down all these different counts? In your head? Pretend you have really bad memory and forget easily, so you don't want to track the counts in your head. Pretend for just a minute that you didn't have a pen and paper handy either. Then, pretend that aside from the box with all the colored balls in it, there's a bunch of other empty boxes sitting off to the corner. How would you refine your strategy now?

1. i would grab a random ball from the box.
2. i would put that ball in one of the empty boxes.
3. i would grab another.
4. if it's the same color, i would put it in the same box as the other one
5. if not, i would put it in a different, empty box.
6. i'd pull another.
7. if it's the same color as one of the other balls, i would put it in the box with the same colored ball
8. if not, i would put it in its own empty box
9. i'd do this until the box with all the balls was empty.
10.I would have as many boxes as there were colors, each containing the amount of balls of the same color, inside.

Junilu Lacar
Bartender
Posts: 7771
62
Bravo, Dan! This is about as good as you can get without actually writing any Java code.

You may have heard the term "data structure" which is simply something that helps you organize and arrange data. In the real-world scenario you just worked through, your data structure consisted of all those boxes. So now, the next step is to translate the "boxes" into some kind of object / data structure in Java.

You already have some experience using arrays and Winston already gave you a hint about Map (Hashmap in particular). If you're not very familiar with Maps/HashMaps, then I suggest simplifying your problem for now. That is, you can come up with a solution using only arrays if you add a constraint that the list can only contain the numbers 1 to 10 or some other finite range that's more to your liking (1..100 maybe?). That is, the range of values that will be in the list is 1..10. An example of a list like this is: {1, 5, 3, 5, 10, 10, 7, 6, 9, 9, 3, 4, 8, 1, 3, 8, 3}. This would be similar to that big box of colored balls. You now need to decide what kind of object you want to use that will be similar to those empty boxes you used to sort the balls by color, only this time you want to sort/count distinct values instead of colors.

Or if you're up for the challenge, go ahead and read up on what a Map is and how it works. This will probably give you the most generic solution without adding the constraint of having a known, finite range of values.

So what would you like to do?

Campbell Ritchie
Sheriff
Posts: 50241
79
Junilu Lacar wrote: . . . read up on what a Map is and how it works. This will probably give you . . .
. . . a really good solution. Take the hint and go through that link.