← 返回编程题库
coding-match-bid-ask-snapshots简单免费版2000ms未尝试

撮合买卖盘快照时间戳

Match Bid and Ask Snapshots

开始编码

在做盘口数据清洗时,常常会遇到这样的场景:买盘(bid)和卖盘(ask)由两条独立的行情链路推送过来,同一“快照”理论上应该几乎同时到达,但实际链路总有抖动,两侧时间戳常常错开几毫秒甚至几十毫秒。为了把它们重新拼回成可分析的盘口快照,我们需要给每一笔 bid 找一个时间戳足够接近的 ask 与之配对。

请实现 solution(bids: list[float], asks: list[float], delta: float) -> list[list[int]]bidsasks 是两条按时间升序排好的时间戳序列,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.00asks[0]=1.02 相差 0.02 ≤ 0.05,配上;接下来 bids[1]=2.00 与剩余的 asks[1]=4.99 相差 2.99,远超容差,且 bids[1] 更早,所以丢弃 bids[1];最后 bids[2]=5.00asks[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 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

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 也能通过。