LeetCode 1661. 每台机器的进程平均运行时间

约 7 分钟
文章信息 6 个分类 1 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 字节跳动
标签
数据库
目录

题目描述

✅ 1661. 每台机器的进程平均运行时间

题意分析

题目目标：Activity 表用 (machine_id, process_id, activity_type, timestamp) 描述事件，每个流程恰好有一条 start 和一条 end。要求输出每台机器上「所有流程耗时」的平均值，保留 3 位小数。

核心约束：一个流程的耗时不是一行数据，而是同一 (machine_id, process_id) 下两行数据的差值；也就是说输入的粒度是「事件」，而答案的粒度是「机器」，中间还夹着一层「流程」。凡是输入粒度和输出粒度不一致的题，都要先想清楚中间那层怎么合并掉。

边界处理：题目保证每个流程都成对出现，所以不必考虑「只有 start 没有 end」的残缺数据；也保证每台机器至少跑过一个流程，因此分母不会为 0。真正要盯住的是小数位数：结果必须是 3 位小数，而不是数据库默认的精度。

实现取舍：把两行合成一行有两条路——自连接（把 start 行和 end 行按键配对）或条件聚合（用 CASE WHEN 把符号翻转后直接求和）。两者结果一致，前者更直白，后者只扫一遍表。

解法：哈希表配对 start/end（代码视角）

核心思路

最朴素的想法是「先按机器分组，再在组内按流程分组，最后在流程里找 end 减 start」——三层嵌套，SQL 写起来会变成子查询套子查询，可读性很差。

瓶颈在于「流程」这一层被当成了一个真实的分组层级。观察一下：每个流程只有两行，且这两行的角色由 activity_type 唯一确定，所以完全不需要真的分组，只要把它们并排放到同一行上，耗时就退化成一次减法。

于是不变量是：自连接之后的结果集里，每一行恰好代表一个完整流程，且该行同时持有它的开始时刻 s.timestamp 与结束时刻 e.timestamp。连接键是 (machine_id, process_id) 这个二元组，它是流程的唯一标识。有了这条不变量，外层就只剩一层 GROUP BY machine_id 的普通平均。

换成代码视角，等价的状态定义是：哈希表 start[(machine_id, process_id)] = timestamp，扫到 end 事件时用 timestamp - start[key] 得到该流程耗时，累加进 total[machine_id] 并让 cnt[machine_id] 自增，最后逐机器输出 total / cnt。SQL 的自连接就是这张哈希表的声明式写法。

解题步骤

第一步：把 Activity 表当成两张表看待。 别名 s 只取 activity_type = 'start' 的行，别名 e 只取 activity_type = 'end' 的行。为什么要起别名：自连接的本质是同一张表扮演两个角色，不起别名数据库无法区分你说的是哪一侧。

第二步：用 machine_id 和 process_id 同时作为连接条件。 只连 machine_id 会让机器上的所有 start 和所有 end 交叉相乘，得到 $k^2$ 行垃圾数据；只连 process_id 会让不同机器上同编号的流程串到一起。两个字段缺一不可，因为流程的唯一标识是这个二元组。

第三步：把 activity_type 的过滤写进 ON 子句。 写在 ON 里意味着「配对时就只认这类行」，配对完成后结果集天然干净；写在 WHERE 里在内连接下等价，但一旦将来改成外连接语义就会变，所以养成写在 ON 里的习惯。

第四步：e.timestamp - s.timestamp 求单个流程耗时，AVG 求机器平均。 此时每行就是一个流程，AVG 的分母自动等于该机器的流程数，不需要再手写 COUNT。

第五步：ROUND(..., 3) 卡住输出精度。 题目明确要求 3 位小数，浮点相减会产生 0.8080000000000001 这类尾巴，不 ROUND 会被判错。

以 Activity = [[0,0,start,0.712], [0,0,end,1.520], [0,1,start,3.140], [0,1,end,4.120], [1,0,start,0.550], [1,0,end,1.550], [1,1,start,0.430], [1,1,end,1.420]] 走一遍：先看自连接的中间结果。s 侧有 4 行（0-0、0-1、1-0、1-1 的 start），e 侧同样 4 行。按 (machine_id, process_id) 配对，每个 s 行只能命中唯一一个 e 行，于是中间结果恰好 4 行：(0, 0, 0.712, 1.520)、(0, 1, 3.140, 4.120)、(1, 0, 0.550, 1.550)、(1, 1, 0.430, 1.420)。注意这里验证了不变量：4 个流程 → 4 行，没有膨胀也没有丢失。

接着算差值列：0.808、0.980、1.000、0.990。再按 s.machine_id 分组：机器 0 拿到 {0.808, 0.980}，平均 (0.808 + 0.980) / 2 = 0.894；机器 1 拿到 {1.000, 0.990}，平均 (1.000 + 0.990) / 2 = 0.995。最后 ROUND 到 3 位，输出 [[0, 0.894], [1, 0.995]]，与期望一致。

代码实现

SELECT
    s.machine_id,
    ROUND(AVG(e.timestamp - s.timestamp), 3) AS processing_time
FROM Activity s
JOIN Activity e
    ON e.machine_id = s.machine_id
    AND e.process_id = s.process_id
    AND s.activity_type = 'start'
    AND e.activity_type = 'end'
GROUP BY s.machine_id;

复杂度分析

  • 时间复杂度：$O(n)$。凭什么：(machine_id, process_id) 是流程的唯一键，等值连接可以走哈希连接，构建哈希表与探测各扫一遍表，分组聚合同样是一次哈希聚合，全程没有嵌套循环，$n$ 为 Activity 的行数。
  • 空间复杂度：$O(n)$。凭什么：哈希连接需要把一侧（约 $n/2$ 行的 start 事件）全部装进哈希表，分组聚合再额外维护机器数量级的累加器，机器数不超过 $n$。

关键点总结

  • 输入粒度和输出粒度不一致时，先补上中间那层。 本题输入是事件、输出是机器、中间是流程，认出这三层之后写法自然收敛为「先把流程拼成一行，再按机器聚合」。
  • 自连接的连接键必须是中间实体的完整主键。 少写一个字段就会产生笛卡尔膨胀，这类 bug 不会报错，只会悄悄把答案改大。
  • 过滤条件优先写进 ON。 内连接下与 WHERE 等价，但语义更贴近「配对规则」，改成外连接时也不会翻车。
  • AVG 天然带分母，别手写除法。 只要保证「一行 = 一个被平均的对象」，AVG 就不会数错个数。
  • 输出精度是题目要求的一部分。 浮点减法的尾差是判错重灾区，ROUND 要写在聚合外层而不是差值里面，否则先舍入再平均会引入额外误差。
  • 面试视角：面试官问这题时，真正想听的是「你能不能把行转列」。先说清楚「一个流程分散在两行，我要把它压成一行」，再给自连接写法，最后主动补一句「也可以用 SUM(CASE WHEN activity_type='end' THEN timestamp ELSE -timestamp END) / COUNT(DISTINCT process_id) 单次扫表完成」，这套「先讲不变量再讲两种实现」的答法比直接甩 SQL 分高得多。

易错点总结

  • 错误写法：ON e.machine_id = s.machine_id 而漏掉 process_id → 用例 machine 0 有 2 个流程时，2 个 start 会分别匹配 2 个 end，中间结果从 2 行膨胀到 4 行，多出 1.520-3.140 = -1.62 这样的负耗时，机器 0 的平均值直接变成负数。
  • 错误写法：ON e.process_id = s.process_id 而漏掉 machine_id → 机器 0 的流程 0 会和机器 1 的流程 0 配对，算出 1.550 - 0.712 这种跨机器耗时，两台机器的结果全部污染。
  • 错误写法：只在 ON 里写 s.activity_type = 'start'，忘了限制 e.activity_type = 'end' → e 侧同时包含 start 和 end 行，每个流程配出 2 行，其中一行差值恒为 0，机器 0 的平均值被拉低成 (0.808 + 0 + 0.980 + 0) / 4 = 0.447。
  • 错误写法：s.timestamp - e.timestamp 把减号方向写反 → 输出 -0.894，符号错误，题目期望正数耗时。
  • 错误写法：省略 ROUND(..., 3) → 机器 0 输出 0.8940000000000001，与期望的 0.894 不匹配被判错。
  • 错误写法：ROUND(e.timestamp - s.timestamp, 3) 写在 AVG 里面 → 先对每个流程舍入再平均，当耗时是 0.8085 这类值时，累积误差会让末位与期望差 1。
  • 错误写法：GROUP BY s.machine_id, s.process_id → 输出粒度变成流程而不是机器，结果行数从 2 行变成 4 行。
  • 错误写法：SELECT machine_id 不加 s. 前缀 → 自连接两侧都有同名列，数据库直接报 Column 'machine_id' in field list is ambiguous。
  • 错误写法：结果列不起别名或起成 avg_time → 判题按列名 processing_time 校验，列名不符直接失败。

相似题目

题目 难度 考察点
175. 组合两个表 简单 用左连接保留无匹配行，而本题的成对数据保证内连接不会丢行
182. 查找重复的电子邮箱 简单 分组后用 HAVING 过滤组，本题分组后直接聚合不需要过滤
197. 上升的温度 简单 同样是自连接，但连接键是「日期相差 1 天」的函数条件而非等值主键
570. 至少有5名直接下属的经理 中等 自连接的两侧是上下级两种角色，聚合的是计数而非平均
1280. 学生们参加各科测试的次数 简单 需要先用交叉连接补全不存在的组合，本题所有组合都真实存在