一种在给定时间间隔内返回唯一用户数的算法

Question

Web服务器可以接收数百万用户登录请求。用户可以多次登录。根据时间复杂度设计一个最优算法/数据结构，以返回给定时间间隔之间的唯一用户总数。

例如:计算间隔t1 & t2和t2 & t3之间的唯一用户总数。还可以考虑返回重叠间隔的总计数(t1 =10 t1，t2 =10:15，t3 =10:30，返回10:10到10:20之间的用户总数)。

下面是我的建议，会感谢大家的评论吗？

Hashmap & min堆的IMO组合将是一个很好的解决方案。

Hashmap-将键作为用户id，值作为指向最小堆中相应节点的节点指针。Min堆-最后一次登录时间作为键，值作为用户id。Root将是其登录时间最长的用户。另外，在根存储区，计算min堆中节点的总数，这样我们就可以快速地返回计数。

1. 当用户登录时。以用户id作为键在hashmap中查找。( a)如果没有匹配，那么将新用户插入hashmap &用户的一个新节点进入min堆，并增加存储在min堆根节点中的计数。( b)否则，它是一个旧用户更新，它是最后一次登录值，不增加最小堆根节点中的计数。
2. 每当我们想找出在t2-t1之间记录的唯一用户，然后从堆中提取min(根)，并检查当前时间-最后一次登录时间> t2-t1分钟。如果它大于删除hashmap & min_heap中的值。重复上述步骤(a)，直到堆的min元素满足当前时间-最后登录时间( <= t2-t1分钟c )。从min堆的根节点返回计数值。

但我无法确定重叠间隔的算法。

Answer 1

我认为有更容易的方法来做这件事。考虑将所有数据存储在一个平衡的二进制搜索树中，其中键是登录时间，值是当时登录的所有人员的列表(假设在同一时刻可以有多个登录)。从这里，您可以通过在BST中查找时间大于或等于T1的最小节点来查找在时间T2和时间间隔内登录的所有人员，然后继续计算该节点的顺序后继，直到您到达一个严格在时间上T2之后的节点。

在BST中查找时间大于或等于T1的第一个节点将花费平衡BST中的时间O(log )，多次计算顺序后继将花费时间O(k)，其中k是报告的匹配总数。这总共需要O(log + k)时间。由于您必须花费至少O(k)时间来报告任何算法中的所有匹配登录，这有一个非常低的开销。

或者，如果您从服务器获取流中的数据(即，新登录总是随着时间的推移而发生)，您可以只使用一个标准数组来保存所有请求。您只需将新请求附加到数组的末尾即可。由于时间总是向前移动的，这意味着数组总是被排序的，所以您可以使用二进制搜索来查找范围的起点。假设数据不是通过病理构造的，您也可以使用插值搜索来使查找时间预期为O(log )，而不是O(log )，在查找k个总元素时给出预期的O(log + k)查找时间。

至于处理重叠范围，有一些标准的算法，用于获取一个范围集合，并将它们合并到最小数量的不重叠范围中。在进行查找之前，您可以始终应用其中一种技术来处理这种情况。

希望这能有所帮助！