当前位置：首页 > article >正文

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

article 2024/10/26 9:20:53

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

实现代码与解析：

滑动窗口

//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;

    }
}

原理思路：

初始化结果数组：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。