Medium

题目描述

设计一个数据结构，用于高效管理网络路由器中的数据包。每个数据包包含以下属性：

  • source: 生成数据包的机器的唯一标识符
  • destination: 目标机器的唯一标识符
  • timestamp: 数据包到达路由器的时间

实现 Router 类：

  • Router(int memoryLimit): 用固定的内存限制初始化路由器对象

    • memoryLimit 是路由器在任何给定时间可以存储的最大数据包数量
    • 如果添加新数据包会超过此限制，必须删除最旧的数据包以释放空间

  • bool addPacket(int source, int destination, int timestamp): 将具有给定属性的数据包添加到路由器

    • 如果路由器中已存在具有相同 source、destination 和 timestamp 的数据包，则认为是重复数据包
    • 如果数据包成功添加（即不是重复的），则返回 true；否则返回 false

  • int[] forwardPacket(): 按 FIFO（先进先出）顺序转发下一个数据包

    • 从存储中删除数据包
    • 将数据包作为数组 [source, destination, timestamp] 返回
    • 如果没有要转发的数据包，返回空数组

  • int getCount(int destination, int startTime, int endTime):

    • 返回当前存储在路由器中（即尚未转发）的数据包数量，这些数据包具有指定的目标地址，且时间戳在包含范围 [startTime, endTime] 内

注意：addPacket 的查询将按时间戳的非递减顺序进行。

示例 1:

输入:
["Router", "addPacket", "addPacket", "addPacket", "addPacket", "addPacket", "forwardPacket", "addPacket", "getCount"]
[[3], [1, 4, 90], [2, 5, 90], [1, 4, 90], [3, 5, 95], [4, 5, 105], [], [5, 2, 110], [5, 100, 110]]

输出:
[null, true, true, false, true, true, [2, 5, 90], true, 1]

约束条件:

  • 2 <= memoryLimit <= 10^5
  • 1 <= source, destination <= 2 * 10^5
  • 1 <= timestamp <= 10^9
  • 1 <= startTime <= endTime <= 10^9
  • 总共最多调用 10^5 次 addPacket、forwardPacket 和 getCount 方法
  • addPacket 的查询将按时间戳的非递减顺序进行

解题思路

这道题需要实现一个路由器数据结构来管理数据包，主要有以下几个关键点：

核心思路

  1. FIFO队列管理: 使用双端队列（deque）来维护数据包的FIFO顺序，支持高效的头部删除和尾部添加操作。

  2. 重复检测: 使用哈希集合存储数据包的唯一标识（source, destination, timestamp的组合），快速检测重复数据包。

  3. 内存限制管理: 当添加新数据包超过内存限制时，自动删除最旧的数据包，同时从哈希集合中移除对应记录。

  4. 高效范围查询: 对于getCount方法，由于时间戳是按非递减顺序添加的，可以使用二分查找快速定位指定目标地址和时间范围内的数据包数量。

数据结构选择

  • 双端队列: 存储实际的数据包信息，支持FIFO操作
  • 哈希集合: 快速检测重复数据包
  • 哈希表: 按目标地址分组存储时间戳，便于范围查询时的二分查找

算法细节

  • addPacket: O(1)时间复杂度，检测重复并维护内存限制
  • forwardPacket: O(1)时间复杂度，简单的队列头部删除
  • getCount: O(log n)时间复杂度，利用二分查找在有序时间戳数组中查找范围

代码实现

class Router {
private:
    int memoryLimit;
    deque<vector<int>> packets;
    unordered_set<string> packetSet;
    unordered_map<int, vector<int>> destinationTimestamps;
    
    string getPacketKey(int source, int destination, int timestamp) {
        return to_string(source) + "_" + to_string(destination) + "_" + to_string(timestamp);
    }
    
public:
    Router(int memoryLimit) : memoryLimit(memoryLimit) {}
    
    bool addPacket(int source, int destination, int timestamp) {
        string key = getPacketKey(source, destination, timestamp);
        if (packetSet.count(key)) {
            return false;
        }
        
        if (packets.size() == memoryLimit) {
            auto oldPacket = packets.front();
            packets.pop_front();
            string oldKey = getPacketKey(oldPacket[0], oldPacket[1], oldPacket[2]);
            packetSet.erase(oldKey);
            
            auto& timestamps = destinationTimestamps[oldPacket[1]];
            timestamps.erase(find(timestamps.begin(), timestamps.end(), oldPacket[2]));
            if (timestamps.empty()) {
                destinationTimestamps.erase(oldPacket[1]);
            }
        }
        
        packets.push_back({source, destination, timestamp});
        packetSet.insert(key);
        destinationTimestamps[destination].push_back(timestamp);
        
        return true;
    }
    
    vector<int> forwardPacket() {
        if (packets.empty()) {
            return {};
        }
        
        auto packet = packets.front();
        packets.pop_front();
        string key = getPacketKey(packet[0], packet[1], packet[2]);
        packetSet.erase(key);
        
        auto& timestamps = destinationTimestamps[packet[1]];
        timestamps.erase(find(timestamps.begin(), timestamps.end(), packet[2]));
        if (timestamps.empty()) {
            destinationTimestamps.erase(packet[1]);
        }
        
        return packet;
    }
    
    int getCount(int destination, int startTime, int endTime) {
        if (destinationTimestamps.find(destination) == destinationTimestamps.end()) {
            return 0;
        }
        
        const auto& timestamps = destinationTimestamps[destination];
        auto start = lower_bound(timestamps.begin(), timestamps.end(), startTime);
        auto end = upper_bound(timestamps.begin(), timestamps.end(), endTime);
        
        return end - start;
    }
};

from collections import deque
import bisect

class Router:
    def __init__(self, memoryLimit: int):
        self.memoryLimit = memoryLimit
        self.packets = deque()
        self.packetSet = set()
        self.destinationTimestamps = {}
    
    def _getPacketKey(self, source: int, destination: int, timestamp: int) -> str:
        return f"{source}_{destination}_{timestamp}"
    
    def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
        key = self._getPacketKey(source, destination, timestamp)
        if key in self.packetSet:
            return False
        
        if len(self.packets) == self.memoryLimit:
            oldPacket = self.packets.popleft()
            oldKey = self._getPacketKey(oldPacket[0], oldPacket[1], oldPacket[2])
            self.packetSet.remove(oldKey)
            
            timestamps = self.destinationTimestamps[oldPacket[1]]
            timestamps.remove(oldPacket[2])
            if not timestamps:
                del self.destinationTimestamps[oldPacket[1]]
        
        self.packets.append([source, destination, timestamp])
        self.packetSet.add(key)
        if destination not in self.destinationTimestamps:
            self.destinationTimestamps[destination] = []
        self.destinationTimestamps[destination].append(timestamp)
        self.destinationTimestamps[destination].sort()
        
        return True
    
    def forwardPacket(self) -> List[int]:
        if not self.packets:
            return []
        
        packet = self.packets.popleft()
        key = self._getPacketKey(packet[0], packet[1], packet[2])
        self.packetSet.remove(key)
        
        timestamps = self.destinationTimestamps[packet[1]]
        timestamps.remove(packet[2])
        if not timestamps:
            del self.destinationTimestamps[packet[1]]
        
        return packet
    
    def getCount(self, destination: int, startTime: int, endTime: int) -> int:
        if destination not in self.destinationTimestamps:
            return 0
        
        timestamps = self.destinationTimestamps[destination]
        start = bisect.bisect_left(timestamps, startTime)
        end = bisect.bisect_right(timestamps, endTime)
        
        return end - start

public class Router {
    private int memoryLimit;
    private Queue<int[]> packets;
    private HashSet<string> packetSet;
    private Dictionary<int, List<int>> destinationTimestamps;
    
    private string GetPacketKey(int source, int destination, int timestamp) {
        return $"{source}_{destination}_{timestamp}";
    }
    
    public Router(int memoryLimit) {
        this.memoryLimit = memoryLimit;
        this.packets = new Queue<int[]>();
        this.packetSet = new HashSet<string>();
        this.destinationTimestamps = new Dictionary<int, List<int>>();
    }
    
    public bool AddPacket(int source, int destination, int timestamp) {
        string key = GetPacketKey(source, destination, timestamp);
        if (packetSet.Contains(key)) {
            return false;
        }
        
        if (packets.Count == memoryLimit) {
            var oldPacket = packets.Dequeue();
            string oldKey = GetPacketKey(oldPacket[0], oldPacket[1], oldPacket[2]);
            packetSet.Remove(oldKey);
            
            var timestamps = destinationTimestamps[oldPacket[1]];
            timestamps.Remove(oldPacket[2]);
            if (timestamps.Count == 0) {
                destinationTimestamps.Remove(oldPacket[1]);
            }
        }
        
        packets.Enqueue(new int[] {source, destination, timestamp});
        packetSet.Add(key);
        if (!destinationTimestamps.ContainsKey(destination)) {
            destinationTimestamps[destination] = new List<int>();
        }
        destinationTimestamps[destination].Add(timestamp);
        destinationTimestamps[destination].Sort();
        
        return true;
    }
    
    public int[] ForwardPacket() {
        if (packets.Count == 0) {
            return new int[0];
        }
        
        var packet = packets.Dequeue();
        string key = GetPacketKey(packet[0], packet[1], packet[2]);
        packetSet.Remove(key);
        
        var timestamps = destinationTimestamps[packet[1]];
        timestamps.Remove(packet[2]);
        if (timestamps.Count == 0) {
            destinationTimestamps.Remove(packet[1]);
        }
        
        return packet;
    }
    
    public int GetCount(int destination, int startTime, int endTime) {
        if (!destinationTimestamps.ContainsKey(destination)) {
            return 0;
        }
        
        var timestamps = destinationTimestamps[destination];
        int start = BinarySearchLeft(timestamps, startTime);
        int end = BinarySearchRight(timestamps, endTime);
        
        return end - start;
    }
    
    private int BinarySearchLeft(List<int> arr, int target) {
        int left = 0, right = arr.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    private int BinarySearchRight(List<int> arr, int target) {
        int left = 0, right = arr.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

var Router = function(memoryLimit) {
    this.memoryLimit = memoryLimit;
    this.packets = [];
    this.packetSet = new Set();
};

Router.prototype.addPacket = function(source, destination, timestamp) {
    const packetKey = `${source}-${destination}-${timestamp}`;
    
    if (this.packetSet.has(packetKey)) {
        return false;
    }
    
    const packet = [source, destination, timestamp];
    this.packets.push(packet);
    this.packetSet.add(packetKey);
    
    if (this.packets.length > this.memoryLimit) {
        const removedPacket = this.packets.shift();
        const removedKey = `${removedPacket[0]}-${removedPacket[1]}-${removedPacket[2]}`;
        this.packetSet.delete(removedKey);
    }
    
    return true;
};

Router.prototype.forwardPacket = function() {
    if (this.packets.length === 0) {
        return [];
    }
    
    const packet = this.packets.shift();
    const packetKey = `${packet[0]}-${packet[1]}-${packet[2]}`;
    this.packetSet.delete(packetKey);
    
    return packet;
};

Router.prototype.getCount = function(destination, startTime, endTime) {
    let count = 0;
    
    for (const packet of this.packets) {
        if (packet[1] === destination && packet[2] >= startTime && packet[2] <= endTime) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间-
空间-