将在过去 k 天内维护前 n 个项目的算法？

Question

我想实现一个维护集合 S 的数据结构对于可以有效回答以下查询同时还具有内存效率的排行榜:

1. add(x, t)添加得分为 x 的新项目设置 S与相关时间 t .

2. query(u)榜首n集合中的项目(按分数排序)S有关联时间t这样 t + k >= u .每个后续查询都会有一个 u不小于之前的查询。

在标准英语中，高分可以单独添加到这个排行榜，我想要一个可以高效查询顶部的算法 n帖子内排行榜上的项目k天(其中 k 和 n 是固定常数)。

n可以假定比项目总数少得多，并且可以假定分数是随机的。

一个朴素的算法是在将所有元素添加到按分数排序的平衡二叉搜索树中时存储所有元素，并在元素超过 k 时从树中删除元素。天大了。检测大于 k 的元素days old 可以用另一个按时间排序的平衡二叉搜索树来完成。该算法将产生良好的时间复杂度 O(log(h))其中 h是过去加分的总数k天。然而，空间复杂度是O(h) ，并且很容易看出，即使没有为下一个 k 添加新分数，大多数保存的数据也永远不会在查询中报告。天。

如果n为 1，一个简单的双端队列就足够了。在将新项目添加到队列的前面之前，从前面删除分数小于新项目的项目，因为它们永远不会在查询中报告。在查询之前，从队列后面移除太旧的项目，然后返回留在队列后面的项目。所有操作都将摊销为常数时间复杂度，我不会存储永远不会报告的项目。

当 n大于 1，我似乎无法制定一个具有良好时间复杂度且仅存储可能报告的项目的算法。一种具有时间复杂度的算法 O(log(h))会很棒，但是 n足够小以至于 O(log(h) + n)也是可以接受的。

有什么想法吗？谢谢!

Answer 1

此解决方案基于双端队列解决方案，我假设 t 是递增的。

思路是，如果有n条记录的t和x都大于它，则可以删除一条记录，这是通过示例代码中的Record.count实现的。

由于每条记录最多会从 S 移动到 temp n 次，因此我们的平均时间复杂度为 O(n)。空间复杂度很难确定。但是，它在模拟中看起来不错。当 h = 10000 且 n = 50 时，S.size() 约为 400。

#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;
}