撮合买卖盘快照时间戳
Match Bid and Ask Snapshots
开始编码在做盘口数据清洗时,常常会遇到这样的场景:买盘(bid)和卖盘(ask)由两条独立的行情链路推送过来,同一“快照”理论上应该几乎同时到达,但实际链路总有抖动,两侧时间戳常常错开几毫秒甚至几十毫秒。为了把它们重新拼回成可分析的盘口快照,我们需要给每一笔 bid 找一个时间戳足够接近的 ask 与之配对。
请实现 solution(bids: list[float], asks: list[float], delta: float) -> list[list[int]]。bids 和 asks 是两条按时间升序排好的时间戳序列,delta 是允许的最大撮合误差(单位与时间戳一致)。返回一个配对列表,每个元素是 [i, j],表示 bids[i] 与 asks[j] 被认为是同一个快照——要求 abs(bids[i] - asks[j]) <= delta,且每个下标最多出现一次。配对策略是自左向右贪心:从最早的两端开始扫,能配就配,然后双方各前进一步;配不上就把更早的那一侧抛弃。
例如 solution([1.00, 2.00, 5.00], [1.02, 4.99, 7.00], 0.05) 应返回 [[0, 0], [2, 1]]:bids[0]=1.00 与 asks[0]=1.02 相差 0.02 ≤ 0.05,配上;接下来 bids[1]=2.00 与剩余的 asks[1]=4.99 相差 2.99,远超容差,且 bids[1] 更早,所以丢弃 bids[1];最后 bids[2]=5.00 与 asks[1]=4.99 相差 0.01,配上。asks[2]=7.00 没有对手方,被丢弃。
朴素的双重循环对 100k × 100k 的输入会爆。请用双指针把整体复杂度压到 O(n + m)。
约束条件
- 0 ≤ len(bids), len(asks) ≤ 100000
- bids 和 asks 都按时间戳升序排列(允许内部出现并列)
- 时间戳是普通的浮点秒数,可正可负,绝对值 ≤ 1e9
- 0.0 ≤ delta ≤ 60.0(典型场景:撮合容差通常是几毫秒到几秒)
- 返回的配对列表按 bid 的下标升序排列;输出的 (i, j) 是 bids/asks 的原始下标,从 0 开始计
样例
Case 1 · example from statement
输入: [[1,2,5],[1.02,4.99,7],0.05]
期望: [[0,0],[2,1]]
bids[0]=1.00 与 asks[0]=1.02 相差 0.02,配对;bids[1]=2.00 与剩余的 asks[1]=4.99 相差 2.99,远超容差,且 bids[1] 更早,被丢弃;bids[2]=5.00 与 asks[1]=4.99 相差 0.01,配对。asks[2]=7.00 没人匹配。
Case 2 · perfect alignment with delta=0
输入: [[10,20,30],[10,20,30],0]
期望: [[0,0],[1,1],[2,2]]
三对时间戳完全相同,差为 0,全部撮合成功,连最严格的 delta=0 也能通过。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · example from statement
输入: [[1,2,5],[1.02,4.99,7],0.05]
期望: [[0,0],[2,1]]
bids[0]=1.00 与 asks[0]=1.02 相差 0.02,配对;bids[1]=2.00 与剩余的 asks[1]=4.99 相差 2.99,远超容差,且 bids[1] 更早,被丢弃;bids[2]=5.00 与 asks[1]=4.99 相差 0.01,配对。asks[2]=7.00 没人匹配。
Case 2 · perfect alignment with delta=0
输入: [[10,20,30],[10,20,30],0]
期望: [[0,0],[1,1],[2,2]]
三对时间戳完全相同,差为 0,全部撮合成功,连最严格的 delta=0 也能通过。