What is the key approach to solving Count Zero Request Servers?

The key approach is array scanning combined with hash table lookups, optimizing it further with sliding window techniques or sorting combined with a two-pointer approach.

How can I optimize my solution for large input sizes?

Use sliding window or sorting and two-pointer techniques to reduce time complexity, ensuring that you avoid redundant operations on large datasets.

What is the sliding window technique in this problem?

The sliding window technique involves maintaining a dynamic range of server request times that can be adjusted as you iterate through queries, allowing for efficient processing.

How do I handle edge cases in Count Zero Request Servers?

Carefully manage time windows, especially for queries where no server receives a request, and ensure that your solution handles the maximum input size efficiently.

What data structures are essential for solving this problem?

Hash tables are used to store server request logs efficiently, and arrays or sliding windows are used to track query results and manage time intervals.

#2747

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

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

数组哈希表滑动窗口排序

题目描述

给你一个整数 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 <= 10⁵
1 <= logs.length <= 10⁵
1 <= queries.length <= 10⁵
logs[i].length == 2
1 <= logs[i][0] <= n
1 <= logs[i][1] <= 10⁶
1 <= x <= 10⁵
x < queries[i] <= 10⁶

lightbulb

解题思路

方法一：离线查询 + 排序 + 双指针

我们可以将所有的查询按照时间从小到大排序，然后按照时间顺序依次处理每个查询。

对于每个查询 $q = (r, i)$ ，其窗口左边界为 $l = r - x$ ，我们需要统计在窗口 $[l, r]$ 内有多少个服务器收到了请求。我们用双指针 $j$ 和 $k$ 分别维护窗口的左右边界，初始时 $j = k = 0$ 。每一次，如果 $k$ 指向的日志的时间小于等于 $r$ ，我们就将其加入到窗口中，然后将 $k$ 向右移动一位。如果 $j$ 指向的日志的时间小于 $l$ ，我们就将其从窗口中移除，然后将 $j$ 向右移动一位。在移动的过程中，我们需要统计窗口中有多少个不同的服务器，这可以使用哈希表来实现。移动结束后，当前时间区间中没有收到请求的服务器数目就是 $n$ 减去哈希表中不同的服务器数目。

时间复杂度 $O(l \times \log l + m \times \log m + n)$ ，空间复杂度 $O(l + m)$ 。其中 $l$ 和 $n$ 分别是数组 $\textit{logs}$ 的长度和服务器的数量，而 $m$ 是数组 $\textit{queries}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def countServers(
        self, n: int, logs: List[List[int]], x: int, queries: List[int]
    ) -> List[int]:
        cnt = Counter()
        logs.sort(key=lambda x: x[1])
        ans = [0] * len(queries)
        j = k = 0
        for r, i in sorted(zip(queries, count())):
            l = r - x
            while k < len(logs) and logs[k][1] <= r:
                cnt[logs[k][0]] += 1
                k += 1
            while j < len(logs) and logs[j][1] < l:
                cnt[logs[j][0]] -= 1
                if cnt[logs[j][0]] == 0:
                    cnt.pop(logs[j][0])
                j += 1
            ans[i] = n - len(cnt)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates strong problem-solving ability by selecting appropriate data structures like hash tables and sliding windows.
question_mark
The candidate efficiently handles large input sizes and provides optimized solutions without redundant operations.
question_mark
The candidate can explain the trade-offs between brute-force and optimized solutions, discussing performance improvements and edge cases.

warning

常见陷阱

外企场景

error
Overlooking time complexity when using brute force, leading to excessive computation for large inputs.
error
Not correctly managing the time window during query processing, which can cause incorrect results for certain edge cases.
error
Failing to optimize space complexity when storing request logs, especially for large datasets.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increase the size of the server pool and logs while maintaining query complexity.
arrow_right_alt
Adjust the query window size dynamically based on server request patterns.
arrow_right_alt
Add constraints where logs include server downtime or maintenance periods that must be considered.

help

常见问题

外企场景

继续练习

#2766 重新放置石块 #2779 数组的最大美丽值 #2780 合法分割的最小下标