双语网站方法,wordpress图片缝隙,中小型网站建设教程,马鞍山广播电视台目录 2747. 统计没有收到请求的服务器数目
题目描述#xff1a;
实现代码与解析#xff1a;
滑动窗口
原理思路#xff1a; 2747. 统计没有收到请求的服务器数目
题目描述#xff1a; 给你一个整数 n #xff0c;表示服务器的总数目#xff0c;再给你一个下标从 0 开…目录 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 1051 logs.length 1051 queries.length 105logs[i].length 21 logs[i][0] n1 logs[i][1] 1061 x 105x 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];// SetInteger 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;}
}
原理思路 初始化结果数组int[] res new int[queries.length]; 创建一个与queries数组长度相同的结果数组res用于存储每个查询的结果。 创建并排序查询索引数组首先创建一个Integer类型的数组ids长度与queries相同用于存储查询的索引。然后对ids进行排序排序依据是queries数组中对应索引的值。这样做的目的是为了按照查询时间的顺序处理查询同时保留原始查询的索引以便将结果放回正确的位置。 对日志进行排序Arrays.sort(logs, (a, b) - a[1] - b[1]); 按照日志中的时间戳对日志数组进行排序确保日志是按时间顺序处理的。 初始化计数数组和双指针int[] cnt new int[n 1]; 创建一个计数数组cnt用于记录每个服务器在当前时间窗口内接收到请求的次数。同时初始化两个指针l左指针和r右指针分别用于维护时间窗口的开始和结束。 遍历查询通过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。
