How to get the prevalance of each number in an array?

Question

I want to get the information of how many times each number has repeated in array. I was doing something like this:

for (int j = 0; j < n; j++){
        cin >> x;
        arr[x]++;
    }

Then I realized the given number may be large as "521659942". And obviously I can't create an array with that size.

arr[x]++;

This is not valid. So what should I do to learn prevalance of each number?

Have you seen [`std::map`](http://en.cppreference.com/w/cpp/container/map) or [`std::unordered_map`](http://en.cppreference.com/w/cpp/container/unordered_map)? — James Adkison, Jan 22 '16 at 13:38

score 2 · Accepted Answer · edited May 23 '17 at 12:15

2

You're essentially using arr[x] as a std::map<int,int>. The index of the array is your key currently, against which you're storing numbers.

Use a map and put values in as you find them. Something like:

encounteredNumbers[key]++;

std::unordered_map and std::map both work here, choosing between them

edited May 23 '17 at 12:15

Community

answered Jan 22 '16 at 13:38

Nathan Cooper

Thanks mate it worked but whenever a number is entered which is entered before, it doesn't count the new one I guess. I think multimap is made for this purpose but I couldn't implement it to my code. map intmap; intmap[x]++; This works but this does not. multimap intmap; intmap[x]++; – K.Yazoglu Jan 22 '16 at 13:58
1

The whole thing you've got in your answer can be shortened to just `encounteredNumbers[key]++;`. – Klitos Kyriacou Jan 22 '16 at 13:58
@K.Yazoglu it works, as count() returns 1 if the value has been entered already, and 0 otherwise. This code is just for entering the data. It doesn't count the number of occurrences. You have to do that yourself in a later piece of code. – Klitos Kyriacou Jan 22 '16 at 14:01

1 Answers1