class Solution {
public:
vector<int> countServers(int n, vector<vector<int>>& logs, int x, vector<int>& queries) {
}
};
6468. 统计没有收到请求的服务器数目
给你一个整数 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 <= 1051 <= logs.length <= 1051 <= queries.length <= 105logs[i].length == 21 <= logs[i][0] <= n1 <= logs[i][1] <= 1061 <= x <= 105x < queries[i] <= 106原站题解
golang 解法, 执行用时: 284 ms, 内存消耗: 28.5 MB, 提交时间: 2023-06-25 09:36:47
func countServers(n int, logs [][]int, x int, queries []int) []int {
sort.Slice(logs, func(i, j int) bool {
return logs[i][1] < logs[j][1]
})
m := len(queries)
arr := make([][]int, m)
for i, q := range queries {
arr[i] = []int{q, i}
}
sort.Slice(arr, func(i, j int) bool {
return arr[i][0] < arr[j][0]
})
res := make([]int, m)
k := len(logs)
var l, r int
hashMap := make(map[int]int)
for _, a := range arr {
q := a[0]
i := a[1]
for r < k && logs[r][1] <= q {
hashMap[logs[r][0]]++
r++
}
for l < r && l < k && logs[l][1] < q-x {
hashMap[logs[l][0]]--
if hashMap[logs[l][0]] == 0 {
delete(hashMap, logs[l][0])
}
l++
}
res[i] = n - len(hashMap)
}
return res
}
java 解法, 执行用时: 47 ms, 内存消耗: 108.9 MB, 提交时间: 2023-06-25 09:35:37
import java.util.*;
class Solution {
public int[] countServers(int n, int[][] logs, int x, int[] queries) {
// 所有日志事件按时间从小到大排序
Arrays.sort(logs, (a, b) -> a[1] - b[1]);
int q = queries.length;
List<Pair<Integer, Integer>> vec = new ArrayList<>();
// 所有询问按结束时间从小到大排序
for (int i = 0; i < q; i++) {
vec.add(new Pair<>(queries[i], i));
}
Collections.sort(vec, (a, b) -> a.getKey() - b.getKey());
int[] ans = new int[q];
// mp[x] 表示服务器 x 在当前区间内收到了几条消息
Map<Integer, Integer> mp = new HashMap<>();
// 双指针
int l = 0, r = 0;
// 按结束时间依次处理每个询问
for (Pair<Integer, Integer> p : vec) {
int curTime = p.getKey();
int idx = p.getValue();
// 区间右端点增加，把时间小于等于右端点的日志加入哈希表
while (r < logs.length && logs[r][1] <= curTime) {
int server = logs[r][0];
mp.put(server, mp.getOrDefault(server, 0) + 1);
r++;
}
// 区间左端点增加，把时间小于左端点的日志踢出哈希表
while (l < logs.length && logs[l][1] < curTime - x) {
int server = logs[l][0];
mp.put(server, mp.getOrDefault(server, 0) - 1);
if (mp.get(server) == 0) {
mp.remove(server);
}
l++;
}
// 题目求的是没有收到日志的服务器数量
ans[idx] = n - mp.size();
}
return ans;
}
}
cpp 解法, 执行用时: 448 ms, 内存消耗: 204.9 MB, 提交时间: 2023-06-25 09:35:15
class Solution {
public:
vector<int> countServers(int n, vector<vector<int>>& logs, int x, vector<int>& queries) {
// 所有日志事件按时间从小到大排序
sort(logs.begin(), logs.end(), [](vector<int> &a, vector<int> &b) {
return a[1] < b[1];
});
int q = queries.size();
typedef pair<int, int> pii;
vector<pii> vec;
// 所有询问按结束时间从小到大排序
for (int i = 0; i < q; i++) vec.push_back(pii(queries[i], i));
sort(vec.begin(), vec.end());
vector<int> ans(q);
// mp[x] 表示服务器 x 在当前区间内收到了几条消息
unordered_map<int, int> mp;
// 双指针
int l = 0, r = 0;
// 按结束时间依此处理每个询问
for (pii p : vec) {
// 区间右端点增加，把时间小于等于右端点的日志加入哈希表
while (r < logs.size() && logs[r][1] <= p.first) mp[logs[r][0]]++, r++;
// 区间左端点增加，把时间小于左端点的日志踢出哈希表
while (l < logs.size() && logs[l][1] < p.first - x) {
int &x = mp[logs[l][0]];
x--;
if (x == 0) mp.erase(logs[l][0]);
l++;
}
// 题目求的是没有收到日志的服务器数量
ans[p.second] = n - (int) mp.size();
}
return ans;
}
};
python3 解法, 执行用时: 328 ms, 内存消耗: 68.4 MB, 提交时间: 2023-06-25 09:34:45
'''
滑动窗口
对请求和问询都排序并滑窗
'''
class Solution:
def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:
ans = [0] * len(queries)
queries = [(x, i) for i, x in enumerate(queries)]
queries.sort()
logs.sort(key=lambda x:(x[1], x[0]))
cnt = defaultdict(lambda:0)
ptr, m = 0, len(logs)
q = deque()
for t, idx in queries:
left, right = t - x, t
while ptr < m and logs[ptr][1] <= right:
q.append(logs[ptr])
cnt[logs[ptr][0]] += 1
ptr += 1
while q and q[0][1] < left:
i, tt = q.popleft()
cnt[i] -= 1
if cnt[i] == 0:del cnt[i]
ans[idx] = n - len(cnt)
return ans