← 返回编程题库
coding-most-frequent-consecutive-event-pair简单免费版2000ms未尝试

订单事件足迹:找出最频繁的连续事件二元组

Order-Event Footprint: Most-Frequent Consecutive Event-Pair

开始编码

实现 solution(events: list[int]) -> list[int]。一段微结构事件日志按到达顺序给出整数事件 id 序列 events(每个 id 表示一种订单生命周期事件——例如 1=Order-Created,2=Order-Modified,3=Order-Cancelled,4=Order-Filled)。在序列上滑动一个长度为 2 的窗口,考察所有 i = 0, 1, ..., N-2 上的连续对 (events[i], events[i+1])。返回出现次数最多的那一对,写成 2 元素列表 [a, b]。若有并列最大值:a 小者胜;若 a 也相等,则 b 小者胜。若 N < 2,不存在任何连续对,返回哨兵 [-1, -1]

例:solution([2, 3, 2, 3, 2, 3, 1]) 返回 [2, 3]。共有 6 个连续对:(2,3)、(3,2)、(2,3)、(3,2)、(2,3)、(3,1);计数分别为 (2,3): 3、(3,2): 2、(3,1): 1,因此 (2,3) 胜出。再看 solution([1, 2, 1, 2, 1]):连续对为 (1,2)、(2,1)、(1,2)、(2,1),(1,2) 与 (2,1) 都出现 2 次,按 a 升序 1 < 2,所以返回 [1, 2]

需要明确的细节:空数组或长度为 1 的输入都不存在连续对,故 solution([])solution([7]) 都返回 [-1, -1];哨兵 [-1, -1] 在长度不足时返回——若 events 本身就含有 -1,(-1, -1) 完全可能是合法的最频繁对(例如 solution([-1, -1, -1, -1]) 应返回 [-1, -1],因为 (-1, -1) 出现 3 次);平局规则只看 key 值,不看首次出现位置,因此不需要额外维护 first_index。

用一个以 (a, b) 整型元组为 key 的字典做一遍线性扫描,再做一次 (count desc, a asc, b asc) 的最值选取即可,整体 O(N) 时间、O(unique_pairs) 额外空间。直接 O(N^2) 的双层重新计数在本题规模下也跑得动,但字典方案更直观、且与复杂度目标一致。

实现细节由 stubs/stub.py 提供。

实践背景

合规与微结构研究在排查"喋喋不休"或"冰山型"挂单足迹时,常常先做这种最朴素的 2-步模式聚合:当 "Order-Modified-then-Cancelled" 这类二元组的占比明显高于更常见的 "Order-Modified-then-Filled" 或 "Order-Created-then-Filled" 时,往往就是 spoofing 类行为的初步信号——算法刚挂上可见报价就立即撤单,意在诱导对手方。把整段日志压缩成"最频繁的连续事件对"是一个刻意做得很轻的摘要:它只用一次线性扫描,就把窗口里最响的 2-步模式定位出来,再决定是否进入更深的序列分析。把平局规则锚到最小 (a, b)(而不是首次出现位置)是为了让同一段窗口在不同顺序回放、或在不同日志分片间重跑时,结果保持一致——结果只依赖于二元组的多重集合,不受下游行序抖动影响。

约束条件

  • 0 <= N <= 5000,其中 N 为 solution(events) 的输入长度
  • 每个 events[i] 为带符号整数,-1000000000 <= events[i] <= 1000000000
  • 若 N < 2(不存在连续二元组),返回 [-1, -1]
  • 否则返回使 (count desc, a asc, b asc) 最大的那个 [a, b]
  • 输出为 2 元素整型列表,按元素精确比对

样例

Case 1 · statement-example: most frequent (2,3) pair

输入: [[2,3,2,3,2,3,1]]

期望: [2,3]

共有 6 个连续对:(2,3)x3、(3,2)x2、(3,1)x1,因此返回 [2, 3]。

Case 2 · visible: tiebreak by smaller a

输入: [[1,2,1,2,1]]

期望: [1,2]

(1,2) 与 (2,1) 都出现 2 次,按 a 升序,1 < 2,所以返回 [1, 2]。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

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

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

Case 1 · statement-example: most frequent (2,3) pair

输入: [[2,3,2,3,2,3,1]]

期望: [2,3]

共有 6 个连续对:(2,3)x3、(3,2)x2、(3,1)x1,因此返回 [2, 3]。

Case 2 · visible: tiebreak by smaller a

输入: [[1,2,1,2,1]]

期望: [1,2]

(1,2) 与 (2,1) 都出现 2 次,按 a 升序,1 < 2,所以返回 [1, 2]。