Get a count of numbers in segments

user_19969699 0
Viewed 40

The array has a large size up to 100000 and m is number of gets.

For example:

int array[] = {1, 2, 2, 3, 4, 5, 5, 5, 6, 7};

get(1, 4, array);

And the result:

1: 1
2: 2
3: 1

I wrote this but it uses a lot of memory:

for (int i=1; i<=n; i++) {
    ma[a[i]]++;
    pref[i] = ma;

}
map<int,int> ans = pref[r];
for (auto i: pref[l - 1]) {
    ans[i.first] -= i.second;
}
for (auto i: ans) {
    cout << i.first << ' ' << i.second << '\n';
}
c++
1 Answers

What's wrong is you're computing the answer for all of the numbers. Instead, do this:

map<int, int> count(int[] array, int left, int right) {
    map<int, int> result;
    for (int i=left; i <= right; i++) {
        result[array[i]]++;
    }
    return result;
}

It's pretty simple; it just iterates over all the indexes and increments the value. Of course, make sure that left and right are within the bounds of the array.

user_198462190
Related