2747. 零请求服务器数量

Medium

题目描述

给你一个整数 n ，表示服务器的总数，以及一个下标从 0 开始的二维整数数组 logs ，其中 logs[i] = [server_id, time] 表示 id 为 server_id 的服务器在时间 time 收到了一个请求。

同时给你一个整数 x 和一个下标从 0 开始的整数数组 queries 。

返回一个长度为 queries.length 的下标从 0 开始的整数数组 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]：服务器 1 和 2 在 [5, 10] 期间收到请求。因此，只有服务器 3 没有收到请求。
对于 queries[1]：只有服务器 2 在 [6,11] 期间收到请求。因此，服务器 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]：只有服务器 3 在 [2,4] 期间没有收到请求。

约束条件：

1 <= n <= 10^5
1 <= logs.length <= 10^5
1 <= queries.length <= 10^5
logs[i].length == 2
1 <= logs[i][0] <= n
1 <= logs[i][1] <= 10^6
1 <= x <= 10^5
x < queries[i] <= 10^6

解题思路

这道题的核心思路是使用排序+滑动窗口的方法来高效处理查询。

基本思路：

对于每个查询 queries[i]，我们需要找出在时间区间 [queries[i] - x, queries[i]] 内没有收到请求的服务器数量
直接暴力查询每个区间会导致时间复杂度过高

优化策略：

预处理查询：将查询按时间排序，同时记录原始索引，便于最后恢复顺序
排序日志：将日志按时间排序，便于使用滑动窗口
滑动窗口维护：对于排序后的查询，使用双指针维护一个时间窗口，窗口内包含所有在当前查询区间内的日志
服务器计数：使用哈希表记录窗口内出现的服务器，零请求服务器数量 = 总服务器数 - 窗口内不重复服务器数

具体实现：

左指针 left 维护窗口左边界，右指针随查询移动
当窗口右移时，添加新的日志记录
当窗口左边界需要收缩时，移除过时的日志记录
使用哈希表的计数功能来跟踪每个服务器在窗口内的请求次数

时间复杂度主要来自排序操作，滑动窗口部分是线性的，整体效率很高。

代码实现

class Solution {
public:
    vector<int> countServers(int n, vector<vector<int>>& logs, int x, vector<int>& queries) {
        // 创建查询索引对，便于排序后恢复原顺序
        vector<pair<int, int>> queryWithIndex;
        for (int i = 0; i < queries.size(); i++) {
            queryWithIndex.push_back({queries[i], i});
        }
        
        // 按查询时间排序
        sort(queryWithIndex.begin(), queryWithIndex.end());
        // 按日志时间排序
        sort(logs.begin(), logs.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        
        vector<int> result(queries.size());
        unordered_map<int, int> serverCount; // 记录窗口内每个服务器的请求次数
        int left = 0;
        
        for (auto& [queryTime, originalIndex] : queryWithIndex) {
            int windowStart = queryTime - x;
            
            // 扩展窗口右边界，添加新的日志
            while (left < logs.size() && logs[left][1] <= queryTime) {
                serverCount[logs[left][0]]++;
                left++;
            }
            
            // 收缩窗口左边界，移除过时的日志
            int right = left - 1;
            while (right >= 0 && logs[right][1] >= windowStart) {
                right--;
            }
            
            // 移除窗口左边界之前的服务器记录
            unordered_map<int, int> validServerCount;
            for (int i = right + 1; i < left; i++) {
                validServerCount[logs[i][0]]++;
            }
            
            // 计算零请求服务器数量
            result[originalIndex] = n - validServerCount.size();
        }
        
        return result;
    }
};

class Solution:
    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:
        # 创建查询索引对，便于排序后恢复原顺序
        query_with_index = [(queries[i], i) for i in range(len(queries))]
        query_with_index.sort()
        
        # 按日志时间排序
        logs.sort(key=lambda log: log[1])
        
        result = [0] * len(queries)
        server_count = {}  # 记录窗口内每个服务器的请求次数
        left = 0
        
        for query_time, original_index in query_with_index:
            window_start = query_time - x
            
            # 扩展窗口右边界，添加新的日志
            while left < len(logs) and logs[left][1] <= query_time:
                server_id = logs[left][0]
                server_count[server_id] = server_count.get(server_id, 0) + 1
                left += 1
            
            # 收缩窗口左边界，移除过时的日志
            right = left - 1
            while right >= 0 and logs[right][1] >= window_start:
                right -= 1
            
            # 统计有效窗口内的服务器
            valid_servers = set()
            for i in range(right + 1, left):
                valid_servers.add(logs[i][0])
            
            # 计算零请求服务器数量
            result[original_index] = n - len(valid_servers)
        
        return result

public class Solution {
    public int[] CountServers(int n, int[][] logs, int x, int[] queries) {
        // 创建查询索引对，便于排序后恢复原顺序
        var queryWithIndex = new List<(int time, int index)>();
        for (int i = 0; i < queries.Length; i++) {
            queryWithIndex.Add((queries[i], i));
        }
        queryWithIndex.Sort();
        
        // 按日志时间排序
        Array.Sort(logs, (a, b) => a[1].CompareTo(b[1]));
        
        int[] result = new int[queries.Length];
        var serverCount = new Dictionary<int, int>(); // 记录窗口内每个服务器的请求次数
        int left = 0;
        
        foreach (var (queryTime, originalIndex) in queryWithIndex) {
            int windowStart = queryTime - x;
            
            // 扩展窗口右边界，添加新的日志
            while (left < logs.Length && logs[left][1] <= queryTime) {
                int serverId = logs[left][0];
                serverCount[serverId] = serverCount.GetValueOrDefault(serverId, 0) + 1;
                left++;
            }
            
            // 收缩窗口左边界，移除过时的日志
            int right = left - 1;
            while (right >= 0 && logs[right][1] >= windowStart) {
                right--;
            }
            
            // 统计有效窗口内的服务器
            var validServers = new HashSet<int>();
            for (int i = right + 1; i < left; i++) {
                validServers.Add(logs[i][0]);
            }
            
            // 计算零请求服务器数量
            result[originalIndex] = n - validServers.Count;
        }
        
        return result;
    }
}

var countServers = function(n, logs, x, queries) {
    // 创建查询索引对，便于排序后恢复原顺序
    const queryWithIndex = queries.map((query, index) => [query, index]);
    queryWithIndex.sort((a, b) => a[0] - b[0]);
    
    // 按日志时间排序
    logs.sort((a, b) => a[1] - b[1]);
    
    const result = new Array(queries.length);
    const serverCount = new Map(); // 记录窗口内每个服务器的请求次数
    let left = 0;
    
    for (const [queryTime, originalIndex] of queryWithIndex) {
        const windowStart = queryTime - x;
        
        // 扩展窗口右边界，添加新的日志
        while (left < logs.length && logs[left][1] <= queryTime) {
            const serverId = logs[left][0];
            serverCount.set(serverId, (serverCount.get(serverId) || 0) + 1);
            left++;
        }
        
        // 收缩窗口左边界，移除过时的日志
        let right = left - 1;
        while (right >= 0 && logs[right][1] >= windowStart) {
            right--;
        }
        
        // 统计有效窗口内的服务器
        const validServers = new Set();
        for (let i = right + 1; i < left; i++) {
            validServers.add(logs[i][0]);
        }
        
        // 计算零请求服务器数量
        result[originalIndex] = n - validServers.size;
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	数值
时间复杂度	O((M + Q) log(M + Q) + M + Q)，其中 M 是日志数量，Q 是查询数量。主要包括排序日志和查询的时间，以及滑动窗口处理的线性时间
空间复杂度	O(M + Q)，用于存储排序后的查询索引对、哈希表记录服务器计数，以及结果数组

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析