LeetCode：2747. 统计没有收到请求的服务器数目（滑动窗口 Java）

目录

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

题目描述：

实现代码与解析：

滑动窗口

原理思路：

---

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

题目描述：

        给你一个整数 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

Related Topics

• 数组
• 哈希表
• 排序
• 滑动窗口

实现代码与解析：

滑动窗口

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int[] countServers(int n, int[][] logs, int x, int[] queries) {int[] res = new int[queries.length];// Set<Integer> set = new HashSet<>();// 新建数组排序id，只queries数组排序会丢失原本顺序Integer[] ids = new Integer[queries.length]; for (int i = 0; i < queries.length; i++) {ids[i] = i;}Arrays.sort(logs, (a, b) -> a[1] - b[1]);Arrays.sort(ids, (a, b) -> queries[a] - queries[b]);int[] cnt = new int[n + 1]; // 记录机器是否在窗口中，因为可能有多个同种机器，所以不能只用set存，要记录一下数量int r = 0, l = 0; // 左右指针int tmp = 0; // 当前窗口中的机器种类for (int id: ids) {while (r < logs.length && logs[r][1] <= queries[id]) {if (cnt[logs[r][0]]++ == 0) {tmp++;}r++;}while (l < logs.length && logs[l][1] < queries[id] - x) {if (cnt[logs[l][0]]-- == 1) {tmp--;}l++;}res[id] = n - tmp;}return res;}
}

原理思路：

1. 初始化结果数组：int[] res = new int[queries.length]; 创建一个与queries数组长度相同的结果数组res，用于存储每个查询的结果。

2. 创建并排序查询索引数组：首先创建一个Integer类型的数组ids，长度与queries相同，用于存储查询的索引。然后，对ids进行排序，排序依据是queries数组中对应索引的值。这样做的目的是为了按照查询时间的顺序处理查询，同时保留原始查询的索引，以便将结果放回正确的位置。

3. 对日志进行排序：Arrays.sort(logs, (a, b) -> a[1] - b[1]); 按照日志中的时间戳对日志数组进行排序，确保日志是按时间顺序处理的。

4. 初始化计数数组和双指针：int[] cnt = new int[n + 1]; 创建一个计数数组cnt，用于记录每个服务器在当前时间窗口内接收到请求的次数。同时初始化两个指针l（左指针）和r（右指针），分别用于维护时间窗口的开始和结束。

5. 遍历查询：通过for (int id: ids)循环遍历排序后的查询索引数组。对于每个查询，执行以下操作：

   • 扩展右边界：通过while循环，将r向右移动，直到logs[r][1]（当前日志的时间戳）大于查询时间queries[id]。如果是服务器首次出现在窗口中（cnt[logs[r][0]]++ == 0），则tmp（当前窗口中的不同服务器数量）增加。
   • 收缩左边界：通过另一个while循环，将l向右移动，直到logs[l][1]小于queries[id] - x（查询时间减去时间间隔）。如果某服务器完全离开窗口（cnt[logs[l][0]]-- == 1），则tmp减少。
   • 计算结果：res[id] = n - tmp; 计算在当前查询时间窗口内没有接收到请求的服务器数量，即总服务器数n减去窗口内有请求的不同服务器数量tmp。