统计没有收到请求的服务器数目
难度:
标签:
题目描述
You are given an integer n denoting the total number of servers and a 2D 0-indexed integer array logs, where logs[i] = [server_id, time] denotes that the server with id server_id received a request at time time.
You are also given an integer x and a 0-indexed integer array queries.
Return a 0-indexed integer array arr of length queries.length where arr[i] represents the number of servers that did not receive any requests during the time interval [queries[i] - x, queries[i]].
Note that the time intervals are inclusive.
Example 1:
Input: n = 3, logs = [[1,3],[2,6],[1,5]], x = 5, queries = [10,11] Output: [1,2] Explanation: For queries[0]: The servers with ids 1 and 2 get requests in the duration of [5, 10]. Hence, only server 3 gets zero requests. For queries[1]: Only the server with id 2 gets a request in duration of [6,11]. Hence, the servers with ids 1 and 3 are the only servers that do not receive any requests during that time period.
Example 2:
Input: n = 3, logs = [[2,4],[2,1],[1,2],[3,1]], x = 2, queries = [3,4] Output: [0,1] Explanation: For queries[0]: All servers get at least one request in the duration of [1, 3]. For queries[1]: Only server with id 3 gets no request in the duration [2,4].
Constraints:
1 <= n <= 1051 <= logs.length <= 1051 <= queries.length <= 105logs[i].length == 21 <= logs[i][0] <= n1 <= logs[i][1] <= 1061 <= x <= 105x < queries[i] <= 106
代码结果
运行时间: 214 ms, 内存: 64.2 MB
/*
思路：
1. 使用Java Stream API和集合操作来优化。
2. 创建一个Map来保存每个服务器的最后请求时间。
3. 遍历查询数组，对每个查询，在相应的时间区间内检查每个服务器是否收到请求。
4. 使用流操作来计算没有收到请求的服务器数量。
*/
import java.util.*;
import java.util.stream.*;
public class ServerRequestsStream {
public int[] countServers(int n, int[][] logs, int x, int[] queries) {
Map<Integer, Integer> lastRequestTime = Arrays.stream(logs)
.collect(Collectors.toMap(log -> log[0], log -> log[1], Math::max));
return Arrays.stream(queries)
.map(query -> {
int startTime = query - x;
return (int) IntStream.rangeClosed(1, n)
.filter(serverId -> lastRequestTime.getOrDefault(serverId, -1) < startTime)
.count();
}).toArray();
}
public static void main(String[] args) {
ServerRequestsStream sr = new ServerRequestsStream();
int n = 3;
int[][] logs = {{1, 3}, {2, 6}, {1, 5}};
int x = 5;
int[] queries = {10, 11};
System.out.println(Arrays.toString(sr.countServers(n, logs, x, queries)));
}
}解释
方法:
本题解采用滑动窗口方法配合双指针技术，对日志进行分析以找出没有收到请求的服务器数。首先，日志按时间进行排序，以便使用双指针滑动窗口来维护时间区间。然后，对查询也进行排序，以便同步处理。在处理过程中，我们维护一个数组cnt，记录每个服务器在当前查询时间窗口内的请求数。同时，用out_of_range记录当前时间窗口内没有收到请求的服务器数量。通过逐步移动两个指针（left和right）来更新这些统计数据——当右指针向右移动时，扩展窗口；当左指针向右移动时，缩小窗口。最终，每次查询的结果即为out_of_range的值。
时间复杂度:
O(m log m + q log q + m)
空间复杂度:
O(n + q)
代码细节讲解
🦆
双指针技术在这个问题中是如何具体应用的？能否详细解释左右指针各自的移动条件和移动时对问题解决的贡献？
▷🦆
在更新服务器的请求计数（cnt数组）时，为什么在cnt[i]为0时减少out_of_range，而在cnt[i]变回0时又增加out_of_range？这种处理方式有什么特别的意义？
▷🦆
如果在查询期间日志数据非常密集，这种双指针滑动窗口方法的效率如何？会不会有性能瓶颈？
▷