本题使用核心代码模式

题目内容

某系统开放了多个 $Test$ 接口供第三方系统调用，同时记录了这些接口的调用信息。存放于日志 $invokes$ 中，$invoke$ 引号 $[time，interfaceId]$，表示在时刻 $time$，接口 $interfaceId$ 被调用了一次。

检查时间窗口长度 $timeSegment$ 。对于某接口，若存在一个时间窗口 $[t，t+timeSegment)$，其被调用的次数不少于 $minLimits$ 次，则称该接口为高频接口。

请你根据这份日志统计出所有高频接口，并按此按钮:若没有，则为空列表 [ ]。

输入描述

第一个参数是 $invokes$，$1<= invokes.length <= 10^5$， $0<= time <= 10^6$ ，$0<= interfaceId<= 10^5$ ，$time$ 递增。

第二个参数是 $timeSegment$，$1<=timeSegment<=10^5$

第三个参数是 $minLimits$，$1<=minLimits<=invokes.length$。

输出描述

全部高频接口的升序列表，可能为空列表 [ ] 。

样例1

输入

[0, 1],[0, 10],[9, 1],[10, 10],[20, 3],[25, 3],[100, 3],[100, 3]
10
2

输出

[1, 3]

说明

共有 $3$ 个接口，分别为 $1、3、10$。

接口 $1$ ：在时间窗口 $[0，0+10)$被调用了两次，分别为时刻 $0$ 和 $9$ ，满足高频接口条件。

接口 $3$ ：在时间窗口 $[100，100 + 10)$ 被调用了两次，满足高频接口条件。还存在其它时间窗口满足高频接口条件，如时间窗口 $[19，29]$ 。

接口 $10$ ：被调用了两次，分别为时刻 $0$ 和 $10$ ，超出了时间窗口，不满足高频接口条件。

模板

Python

'''
class InvokeInfo:
    def __init__(self, interface_id: int, time: int):
        self.interface_id = interface_id
        self.time = time
'''
from typing import List
from invoke_info import InvokeInfo 

def get_interfaces(invokes: List[InvokeInfo], time_segment: int, min_limits: int) -> List[int]:
    

Java

/*
public class InvokeInfo {
    int interfaceId;
    int time;
    
    public InvokeInfo(int interfaceId, int time) {
        this.interfaceId = interfaceId;
        this.time = time;
    }
}
*/
import java.util.*;

class Solution {
    public List<Integer> getInterfaces(List<InvokeInfo> invokes, int timeSegment, int minLimits) {
    }
}

C++

/*
struct InvokeInfo {
    int interfaceId;
    int time;
    InvokeInfo(int id, int t)
        : interfaceId(id), time(t) {}
};
*/
#include<bits/stdc++.h>
#include "InvokeInfo.h"  
using namespace std;

class Solution {
    public:
        vector<int> getInterfaces(vector<InvokeInfo>& invokes, int timeSegment, int minLimits) {
           
        }
};

题解

题目描述

某系统开放了多个 $Test$ 接口供第三方系统调用，同时记录了这些接口的调用信息。存放于日志 $invokes$ 中，$invoke$ 引号 $[time，interfaceId]$，表示在时刻 $time$，接口 $interfaceId$ 被调用了一次。

检查时间窗口长度 $timeSegment$ 。对于某接口，若存在一个时间窗口 $[t，t+timeSegment)$，其被调用的次数不少于 $minLimits$ 次，则称该接口为高频接口。

请你根据这份日志统计出所有高频接口，并按此按钮:若没有，则为空列表 [ ]。

输入描述

第一个参数是 $invokes$，$1<= invokes.length <= 10^5$， $0<= time <= 10^6$ ，$0<= interfaceId<= 10^5$ ，$time$ 递增。

第二个参数是 $timeSegment$，$1<=timeSegment<=10^5$

第三个参数是 $minLimits$，$1<=minLimits<=invokes.length$。

输出描述

• 全部高频接口的升序列表，可能为空列表 [ ]。

解题思路

1. 输入解析与数据存储

   • 我们需要从 invokes 中提取每个接口的调用时间。为此，我们可以使用一个字典（哈希表）来存储每个 interfaceId 对应的调用时间列表。这样就可以快速访问每个接口的所有调用记录。

2. 滑动窗口技术

   • 对于每个接口，我们需要检查它的调用时间是否满足高频接口的条件。具体来说，我们需要使用滑动窗口（Sliding Window）技术来检查每个接口的调用时间：
     • 滑动窗口定义：我们使用两个指针（left 和 right）来维护一个时间窗口 [times[left], times[right]]，其中 times[left] 是窗口的最左端时间，times[right] 是窗口的最右端时间。
     • 如果窗口的时间差小于 timeSegment，并且窗口内的调用次数大于等于 minLimits，则该接口是高频接口。

3. 排序

   • 最后，将所有高频接口按升序排列并返回。

复杂度分析

• 时间复杂度：

  • 分类存储接口调用时间：遍历 invokes 列表，时间复杂度为 O(n)，其中 n 是调用记录的总数。
  • 滑动窗口：对于每个接口，调用时间列表的滑动窗口操作的时间复杂度是 O(m)，其中 m 是该接口的调用次数。假设接口的数量为 k，则滑动窗口操作的总时间复杂度为 O(k * m)。
  • 排序：对高频接口进行排序，时间复杂度为 O(k log k)，其中 k 是高频接口的数量。

  总的时间复杂度是 O(n + k log k)，其中 n 是总调用次数，k 是高频接口的数量。

• 空间复杂度：

  • 存储调用时间的字典和中间结果的列表，空间复杂度为 O(n)。

Python 代码

from typing import List
from invoke_info import InvokeInfo  # 导入InvokeInfo类，假设该类包含接口调用信息

def get_interfaces(invokes: List[InvokeInfo], time_segment: int, min_limits: int) -> List[int]:
    # 第一步：根据接口ID将调用时间组织成字典形式
    interface_map = {}  # 创建一个字典来存储接口ID和对应的调用时间列表
    for invoke in invokes:
        if invoke.interface_id not in interface_map:
            interface_map[invoke.interface_id] = []  # 如果接口ID不存在，则初始化一个空列表
        interface_map[invoke.interface_id].append(invoke.time)  # 将每次调用的时间添加到对应接口的列表中
    
    result = []  # 用于存储高频接口ID的结果列表
    # 第二步：对于每个接口ID，首先对调用时间进行排序，然后检查是否符合高频接口条件
    for interface_id, times in interface_map.items():
        times.sort()  # 对当前接口的调用时间进行升序排序
        
        dist = float('inf')  # 初始化距离为正无穷，表示最初还没有找到合适的时间间隔
        
        # 对于每个接口ID，检查最小时间间隔
        for i in range(min_limits - 1, len(times)):
            # 计算窗口大小为min_limits的时间段内的最小时间间隔
            dist = min(dist, times[i] - times[i - min_limits + 1])
        
        # 如果最小时间间隔小于给定的时间窗口time_segment，则认为该接口是高频接口
        if dist < time_segment:
            result.append(interface_id)  # 将该接口ID加入结果列表
    
    return sorted(result)  # 返回按升序排序的高频接口ID列表

Java 代码

import java.util.*;

class Solution {
    public List<Integer> getInterfaces(List<InvokeInfo> invokes, int timeSegment, int minLimits) {
        // 使用 HashMap 存储接口ID及其对应的调用时间列表
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        
        // 遍历所有的调用记录，将接口ID与对应的调用时间存入 map
        for (InvokeInfo info : invokes) {
            // computeIfAbsent 方法：如果接口ID不存在，则创建一个新的 ArrayList 并添加调用时间
            map.computeIfAbsent(info.interfaceId, key -> new ArrayList<>()).add(info.time);
        }

        // 用于存储符合条件的高频接口ID
        List<Integer> ls = new ArrayList<Integer>();

        // 遍历 map 中的每个接口ID及其调用时间列表
        for (Map.Entry<Integer, ArrayList<Integer>> entry : map.entrySet()) {
            Integer interfaceId = entry.getKey();  // 当前接口的ID
            ArrayList<Integer> list = entry.getValue();  // 当前接口的调用时间列表

            // 对当前接口的调用时间进行升序排序
            Collections.sort(list);

            // 初始化距离为一个非常大的数（正无穷），用于比较时间差
            int dist = 0x3f3f3f3f;  // 0x3f3f3f3f 是一个很大的数，表示正无穷

            // 使用滑动窗口来检查最小时间间隔，保证窗口内的调用次数不小于 minLimits
            for (int i = minLimits - 1; i < list.size(); i++) {
                // 计算滑动窗口内的时间差，即当前时间与最早时间的差距
                dist = Math.min(dist, list.get(i) - list.get(i - minLimits + 1));
            }

            // 如果最小的时间间隔小于给定的时间窗口 timeSegment，说明这是一个高频接口
            if (dist < timeSegment) {
                ls.add(interfaceId);  // 将该接口ID加入结果列表
            }
        }

        // 返回结果列表，其中包含所有高频接口ID，默认按升序排列
        return ls;
    }
}

C++ 代码

#include<bits/stdc++.h>
#include "InvokeInfo.h"  //InvokeInfo.h 定义了 InvokeInfo 类，该类包含接口调用信息
using namespace std;

class Solution {
    public:
        // 函数：获取所有高频接口
        vector<int> getInterfaces(vector<InvokeInfo>& invokes, int timeSegment, int minLimits) {
            // 使用 unordered_map 存储每个接口的调用时间
            unordered_map<int, vector<int>> map;

            // 遍历所有调用记录，将每个接口的调用时间加入到 map 中
            for (const InvokeInfo& info : invokes) {
                map[info.interfaceId].push_back(info.time);  // 将每个接口的时间记录到对应的列表中
            }

            vector<int> result;  // 用于存储所有高频接口ID的结果列表

            // 遍历 map 中的每个接口ID及其对应的时间列表
            for (auto& entry : map) {
                int interfaceId = entry.first;  // 获取当前接口的ID
                vector<int>& times = entry.second;  // 获取当前接口的所有调用时间列表

                // 对调用时间进行排序
                sort(times.begin(), times.end());

                int dist = INT_MAX;  // 初始化最小时间间隔为最大值（INT_MAX）
                
                // 滑动窗口：查找最小的时间间隔，保证至少有 minLimits 次调用
                for (int i = minLimits - 1; i < times.size(); i++) {
                    // 计算窗口内的时间差：窗口内最远时间与最短时间的差
                    dist = min(dist, times[i] - times[i - minLimits + 1]);
                }

                // 如果最小时间间隔小于给定的时间窗口，则认为该接口是高频接口
                if (dist < timeSegment) {
                    result.push_back(interfaceId);  // 将该接口ID加入结果列表
                }
            }

            // 将结果列表按升序排序
            sort(result.begin(), result.end());

            // 返回升序排列的高频接口ID列表
            return result;
        }
};