统计没有收到请求的服务器数目

标签: 数组 哈希表 排序 滑动窗口

难度: Medium

给你一个整数 n ，表示服务器的总数目，再给你一个下标从 0 开始的 二维 整数数组 logs ，其中 logs[i] = [server_id, time] 表示 id 为 server_id 的服务器在 time 时收到了一个请求。

同时给你一个整数 x 和一个下标从 0 开始的整数数组 queries  。

请你返回一个长度等于 queries.length 的数组 arr ，其中 arr[i] 表示在时间区间 [queries[i] - x, queries[i]] 内没有收到请求的服务器数目。

注意时间区间是个闭区间。

示例 1：

输入：n = 3, logs = [[1,3],[2,6],[1,5]], x = 5, queries = [10,11]
输出：[1,2]
解释：
对于 queries[0]：id 为 1 和 2 的服务器在区间 [5, 10] 内收到了请求，所以只有服务器 3 没有收到请求。
对于 queries[1]：id 为 2 的服务器在区间 [6,11] 内收到了请求，所以 id 为 1 和 3 的服务器在这个时间段内没有收到请求。

示例 2：

输入：n = 3, logs = [[2,4],[2,1],[1,2],[3,1]], x = 2, queries = [3,4]
输出：[0,1]
解释：
对于 queries[0]：区间 [1, 3] 内所有服务器都收到了请求。
对于 queries[1]：只有 id 为 3 的服务器在区间 [2,4] 内没有收到请求。

提示：

  • 1 <= n <= 105
  • 1 <= logs.length <= 105
  • 1 <= queries.length <= 105
  • logs[i].length == 2
  • 1 <= logs[i][0] <= n
  • 1 <= logs[i][1] <= 106
  • 1 <= x <= 105
  • x < queries[i] <= 106

Submission

运行时间: 214 ms

内存: 64.2 MB

class Solution:
    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:
        logs.sort(key=lambda p: p[1])  # 按照 time 排序
        ans = [0] * len(queries)
        cnt = [0] * (n + 1)
        out_of_range = n
        left = right = 0
        m = len(logs)
        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):
            while right < m and logs[right][1] <= q:  # 进入窗口
                i = logs[right][0]
                if cnt[i] == 0: out_of_range -= 1
                cnt[i] += 1
                right += 1
            while left < m and logs[left][1] < q - x:  # 离开窗口
                i = logs[left][0]
                cnt[i] -= 1
                if cnt[i] == 0: out_of_range += 1
                left += 1
            ans[qi] = out_of_range
        return ans

Explain

本题解采用滑动窗口方法配合双指针技术，对日志进行分析以找出没有收到请求的服务器数。首先，日志按时间进行排序，以便使用双指针滑动窗口来维护时间区间。然后，对查询也进行排序，以便同步处理。在处理过程中，我们维护一个数组cnt，记录每个服务器在当前查询时间窗口内的请求数。同时，用out_of_range记录当前时间窗口内没有收到请求的服务器数量。通过逐步移动两个指针（left和right）来更新这些统计数据——当右指针向右移动时，扩展窗口；当左指针向右移动时，缩小窗口。最终，每次查询的结果即为out_of_range的值。

时间复杂度: O(m log m + q log q + m)

空间复杂度: O(n + q)

class Solution:
    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:
        logs.sort(key=lambda p: p[1])  # 按照时间排序日志
        ans = [0] * len(queries)
        cnt = [0] * (n + 1)
        out_of_range = n
        left = right = 0
        m = len(logs)
        for qi, q in sorted(enumerate(queries), key=lambda p: p[1]):
            while right < m and logs[right][1] <= q:  # 将右指针移至不超过当前查询时间的最远位置
                i = logs[right][0]
                if cnt[i] == 0: out_of_range -= 1 # 如果该服务器之前未收到请求，更新未收到请求的服务器数量
                cnt[i] += 1
                right += 1
            while left < m and logs[left][1] < q - x:  # 将左指针移至小于当前查询时间窗口的最远位置
                i = logs[left][0]
                cnt[i] -= 1
                if cnt[i] == 0: out_of_range += 1 # 如果该服务器现在未收到请求，更新未收到请求的服务器数量
                left += 1
            ans[qi] = out_of_range # 记录结果
        return ans

Explore

在本题中，双指针技术用于维护一个时间窗口，该窗口内的日志表示在当前查询时间内服务器接收到的请求。左指针和右指针分别表示窗口的开始和结束。右指针向右移动时，扩展窗口以包括所有不超过当前查询时间的请求，增加相应服务器的请求计数，并适当调整没有收到请求的服务器数量。当服务器从未收到请求到收到请求时，该服务器不再被计入未收到请求的服务器数，因此需要减少out_of_range的值。左指针向右移动时，缩小窗口以排除早于当前查询时间窗口的请求，减少相应服务器的请求计数，并适当调整没有收到请求的服务器数量。当服务器的请求计数重新变为零时，意味着它在当前查询窗口内没有任何请求，因此需要增加out_of_range的值。这种双指针的运用确保了我们能够有效地根据时间窗口更新每个服务器的请求状态，从而在每次查询时都能准确计算出未收到请求的服务器数量。

数组cnt用于记录每个服务器在当前查询时间窗口内的请求计数。当cnt[i]为0时表示该服务器在当前窗口内尚未收到任何请求，因此是计入out_of_range的一个。如果此时这个服务器接收到了一个请求，其cnt[i]从0变为1，因此需要从out_of_range中减去这个服务器，因为它不再是未收到请求的服务器。相反，当一个服务器在时间窗口调整后（左指针移动）其请求计数重新变为0，说明它在新的时间窗口内没有收到任何请求，因此需要重新将这个服务器计入out_of_range。这种处理确保out_of_range始终准确反映当前查询时间窗口内未收到请求的服务器总数。

当日志数据非常密集时，右指针可能频繁向右移动，而每次移动都需要更新服务器的请求计数和out_of_range值。虽然这种情况下双指针方法可能会有较高的运算量，但整体效率仍然相对较高，因为每个日志只被处理两次（一次由右指针处理，一次由左指针处理），因此时间复杂度为O(m + q)，其中m是日志条数，q是查询次数。然而，在极端情况下，例如日志非常密集且服务器数量很大时，频繁更新cnt数组和计算out_of_range可能会导致性能瓶颈。在这种情况下，可能需要考虑更高效的数据结构或优化算法来进一步提升性能。