服务器请求统计 - 滑动窗口和哈希表算法
思路:滑动窗口+哈希表
使用一个哈希表记录每个时间点的请求情况,key为时间点,value为一个集合,表示在该时间点请求的所有服务器。对于每个查询,我们需要找到在查询时间区间内没有请求的服务器数量,可以通过滑动窗口来实现。我们维护一个窗口,窗口大小为x,开始时间为当前查询时间- x,结束时间为当前查询时间。我们先将窗口内的所有请求加入到一个集合中,然后遍历所有的服务器,如果该服务器没有在集合中出现过,则表示在窗口时间内没有请求该服务器,将计数器加1即可。
时间复杂度:O(n+m),其中n为logs数组的长度,m为queries数组的长度。遍历logs数组需要O(n)的时间,遍历queries数组需要O(m)的时间,对于每个查询,需要遍历窗口内的所有请求和所有服务器,时间复杂度均为O(n)。因此总时间复杂度为O(n+m+n×m)=O(n×m)。
空间复杂度:O(n),哈希表用于存储所有请求的情况,最坏情况下需要存储n个请求。
原文地址: https://www.cveoy.top/t/topic/oTiT 著作权归作者所有。请勿转载和采集!