Count Similar iTems in Array

Question

Hi guys,

I need to count the similar elements in an array. For example, if i have an array, array[0,0,0,1,2,3,3].The number of 0's are 3 , no. of 1's are 1 , no. of 2's are 1 , no. of 3's are 2 in this array . I am sorry if this message has been posted before. Help is appreciated. Thanks in advance.

Regards,

THM

P.S : Language is C/C++

Answer 1

You could use a std::map to store and adapt your results based on the array-entry, while iterating over the array. I hope this hint helps for your assignment.

Answer 2

Is the array sorted? Can you use another data structure? e.g. a map, vector, etc.

Answer 3

Ah, I assume this is a homework then. Correct me if I'm mistaken.

How would you do if I'd ask you to implement the algorithm? You can see from your sample input that it's easier to count the members of each group when the input is grouped, rather than shuffled in arbitrary order. If you sort the input then you'll get the various elements grouped. Then you will just need to iterate over the sequence once in order to count the members of each group.

When you have the algorithm working, try to refine it such that it never reads an element of the input sequence more than once. If you can satisfy the guarantee that each element is read exactly once, and that the elements are read in order from begin to end then your algorithm will work on input coming directly from an input stream such as stdin (so long as it is coming sorted), with no need to first copy the input from the input stream to a temporary container.

Answer 4

I can think of a few options:

1. Copy the array into a std::multiset<> and then use the count() or equal_range() member functions to return the counts

2. Create a std::map<T,unsigned>. The map key (of your array entry type T, which will be an integral type from your example) is the array entry, the value is the count. Increment the count associated with a value every time you encounter an element with that value as you iterate through the array

3. If the array is sorted use std::equal_range() to find consecutive equal elements, and count them.

There are of course many more, including just iterating though and counting directly.