过去k天中保持前n个项目的算法？

Question

过去k天中保持前n个项目的算法？

3

我希望实现一种数据结构用于维护一个称为排行榜的集合 S，该数据结构需要能够有效地回答以下查询并具有较高的内存效率：

1. add(x, t) - 将得分为 x 的新项添加到与时间 t 相关联的集合 S 中。 2. query(u) - 列出在 t + k >= u 时与时间 t 相关联的集合 S 中前 n 个项目（按分数排序）。每个后续查询将具有不小于之前查询的 u。

在标准英语中，可以将高分单独添加到此排行榜中，并需要一种能够快速查询排行榜中前 n 个项目的算法，在 post k 天内（其中 k 和 n 是固定常数）。

假定 n 远小于总项目数，也可以假定分数是随机的。

一种朴素的算法是将所有元素作为它们添加到平衡二叉搜索树中，并按分数排序。当它们超过 k 天时，从树中删除元素。通过另一个按时间排序的平衡二叉搜索树来检测超过 k 天的元素。该算法将产生良好的时间复杂度O（log（h）），其中 h 是过去 k 天中添加的总得分数量。然而，空间复杂度为O（h），并且即使在接下来的 k 天内没有添加新得分，大多数存储数据也不会在查询中报告。

如果 n=1，则只需要一个简单的双端队列。在将新项添加到队列前端之前，请从前面删除得分小于新项的项目，因为它们永远不会在查询中报告。在查询之前，请从队列后面删除过时的项目，然后返回队列后面剩余的项目。所有操作都可以平均常量时间完成，并且我不会存储永远不会报告的项目。

当 n 大于 1 时，我无法构建具有良好时间复杂度并仅存储可能报告的项目的算法。具有时间复杂度 O（log（h））的算法是很棒的，但是 n 足够小，可以接受 O（log（h）+n）。有任何想法？谢谢！

- Bernard

一个想法：制作四叉树。 - user31264

我们也可以考虑k很小吗？ - Petar Petrovic

@PetarPetrovic 因为我要按秒计数而不是天，所以k会很大，可能比h大。 - Bernard

如果t始终增加而x始终减少，则会报告每个(x, t)。因此，我猜没有算法可以使最坏情况的空间复杂度小于O(h)。 - Mo Tao

1

@MoTao 我知道这一点，所以我提到分数可以假设为随机的。虽然最坏情况下的空间复杂度不会小于O(h)，但平均空间复杂度可能会小得多。 - Bernard

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mo Tao · Accepted Answer

这个解决方案基于双向队列的解决方案，并且我假设t是升序的。思路是，如果有n条记录的t和x都比它大，那么就可以删除一条记录，这在示例代码中通过Record.count实现。由于每个记录最多从S移动到tempn次，因此平均时间复杂度为O(n)。空间复杂度很难确定。但是，在模拟中看起来还不错。S.size()约为400，当h = 10000且n = 50时。

#include <iostream>
#include <vector>
#include <queue>
#include <cstdlib>
using namespace std;

const int k = 10000, n = 50;

class Record {
public:
    Record(int _x, int _t): x(_x), t(_t), count(n) {}
    int x, t, count;
};

deque<Record> S;

void add(int x, int t)
{
    Record record(x, t);
    vector<Record> temp;
    while (!S.empty() && record.x >= S.back().x) {
        if (--S.back().count > 0) temp.push_back(S.back());
        S.pop_back();       
    }
    S.push_back(record);
    while (!temp.empty()) {
        S.push_back(temp.back());
        temp.pop_back();
    }
}

vector<int> query(int u)
{
    while (S.front().t + k < u)
        S.pop_front();
    vector<int> xs;
    for (int i = 0; i < S.size() && i < n; ++i)
        xs.push_back(S[i].x);
    return xs;
}

int main()
{
    for (int t = 1; t <= 1000000; ++t) {
        add(rand(), t);
        vector<int> xs = query(t);
        if (t % k == 0) {
            cout << "t = " << t << endl;
            cout << "S.size() = " << S.size() << endl;
            for (auto x: xs) cout << x << " ";
            cout << endl;
        }
    }

    return 0;
}