algorithm - 有效地计算给定范围内每个元素的出现次数

Question

所以我有一些这样的范围:

2 4
1 9
4 5
4 7

为此结果应该是

1 -> 1
2 -> 2
3 -> 2
4 -> 4
5 -> 3  
6 -> 2
7 -> 2
8 -> 1
9 -> 1

天真的方法是遍历所有范围，但效率非常低，最坏的情况是 O(n * n)

什么是 O(n) 或 O(log(n)) 的有效方法

Answer 1

这是 O(n) 中的解决方案:

基本原理是在a中添加一个范围[a, b]作为+1，在b之后添加一个-1。然后，在添加所有范围后，计算该数组的累加和并显示它。

如果您需要在添加值时执行查询，更好的选择是使用二叉索引树，但您的问题似乎不需要这样做，所以我将其省略。

#include <iostream>
#define MAX 1000
using namespace std;

int T[MAX];

int main() {
    int a, b;
    int min_index = 0x1f1f1f1f, max_index = 0;
    while(cin >> a >> b) {
        T[a] += 1;
        T[b+1] -= 1;
        min_index = min(min_index, a);
        max_index = max(max_index, b);
    }

    for(int i=min_index; i<=max_index; i++) {
        T[i] += T[i-1];   
        cout << i << " -> " << T[i] << endl;
    }
}

更新:基于 גלעד ברקן 的“挑衅”(从好的意义上说)，您也可以在 O(n log n) 中执行此操作:

#include <iostream>
#include <map>
#define ull unsigned long long
#define miit map<ull, int>::iterator
using namespace std;

map<ull, int> T;

int main() {
    ull a, b;
    while(cin >> a >> b) {
        T[a] += 1;
        T[b+1] -= 1;
    }

    ull last;
    int count = 0;
    for(miit it = T.begin(); it != T.end(); it++) {
        if (count > 0)
            for(ull i=last; i<it->first; i++)
                cout << i << " " << count << endl;
        count += it->second;
        last = it->first;
    }
}

此解决方案的优点是能够支持具有更大值的范围(只要输出不是那么大)。