LeetCode 1126. 查询活跃业务

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

题目描述

✅ 1126. 查询活跃业务

题意分析

Events 表的每一行是「某个业务（business_id）在某类事件（event_type）上发生了多少次（occurrences）」，(business_id, event_type) 是主键。定义：若某业务在某类事件上的 occurrences 严格大于该事件类型在全表上的平均出现次数，就说这个业务在该事件类型上「活跃」；如果一个业务在多于一种事件类型上活跃，它就是活跃业务。要求返回所有活跃业务的 business_id。

这段定义里藏着三个必须逐字落实的点。第一，比较的基准是按事件类型分别计算的平均值，不是全表一个总平均——每种 event_type 有自己的门槛。第二，比较是严格大于，等于平均值不算活跃。第三，「多于一种」是 > 1，也就是至少两种，不是 >= 1。

主键是 (business_id, event_type) 这个信息很关键：它保证同一个业务在同一事件类型上只有一行，因此后面统计「活跃的事件类型数」时可以直接 COUNT(*)，不需要 COUNT(DISTINCT event_type) 来防重。

结构上，这是一个典型的「先算出分组级别的统计量，再回过头来筛选明细行」的问题：平均值是 event_type 粒度的聚合，而筛选发生在原始的 (business_id, event_type) 粒度上。两个粒度不同，所以必然需要把聚合结果与明细表关联起来。

边界：可能没有任何业务满足条件，此时返回空结果集即可；题目未要求排序，任意顺序均可；occurrences 是正整数，平均值可能是小数，比较时不能取整。

解法：SQL 查询建模

核心思路

比较门槛按 event_type 聚合，最终答案却按 business_id 聚合，两个粒度不同，不能在一层 GROUP BY 中完成。

先生成 event_avg(event_type, avg_occurrences)，其中每种事件恰好一行；再按 event_type 连接回 Events，使每条业务事件记录拿到对应类型的平均值。用 WHERE e.occurrences > a.avg_occurrences 过滤后，保持以下不变量：

结果中的每一行，恰好表示一个业务在一种事件类型上超过了该类型平均值。

最后按 business_id 分组并要求 COUNT(*) > 1。表的主键是 (business_id, event_type)，所以同一业务的同一事件类型最多贡献一行，COUNT(*) 正好等于该业务超过平均值的事件类型数，不需要 DISTINCT。

正确性由三步对应关系保证：子查询为每种事件算出唯一且完整的平均值；等值连接让每条明细只与自己的事件类型门槛比较；严格过滤后按业务计数，恰好保留满足“超过平均值的事件类型多于一种”的业务。

解题步骤

  1. 子查询按 event_type 分组，计算 AVG(occurrences)，得到每种事件的比较门槛。
  2. 通过 a.event_type = e.event_type 把门槛等值连接回明细表。子查询中 event_type 唯一，因此连接不会重复明细行。
  3. 在 WHERE 中保留 occurrences 严格大于对应平均值的行；等于平均值不算。
  4. 按 business_id 分组，在 HAVING 中保留 COUNT(*) > 1 的组。

题目样例中，reviews、ads、page views 的平均值分别为 5、8、7.5。过滤后业务 1 命中 reviews 和 ads 两种，业务 2 只命中 page views 一种，因此只有业务 1 被返回。

代码实现

SELECT e.business_id
FROM Events e
JOIN (
    SELECT event_type, AVG(occurrences) AS avg_occurrences
    FROM Events
    GROUP BY event_type
) a ON a.event_type = e.event_type
WHERE e.occurrences > a.avg_occurrences
GROUP BY e.business_id
HAVING COUNT(*) > 1;

复杂度分析

  • 时间复杂度：逻辑上是常数次扫描、两次分组和一次等值连接。哈希执行计划的期望时间为 $O(n)$；若分组或连接需要排序，最坏为 $O(n\log n)$。
  • 空间复杂度：哈希执行计划约为 $O(t+b)$，其中 $t$ 是事件类型数、$b$ 是业务数；实际复杂度由数据库执行计划和索引决定。

关键点总结

  • 门槛粒度与输出粒度不同：先按 event_type 算门槛，再按 business_id 计数。
  • WHERE 负责过滤单条业务事件，HAVING 负责过滤聚合后的业务组。
  • 连接条件必须是 event_type，否则明细会拿错平均值或形成笛卡尔积。
  • 主键唯一性保证 COUNT(*) 就是活跃事件类型数。
  • 两个条件都是严格大于：occurrences > average 且活跃类型数 > 1；平均值不能取整。

易错点总结

  • 用全表平均值代替按 event_type 的平均值。样例三类门槛分别是 5、8、7.5，不能合并成一个数。
  • 写成 occurrences >= avg_occurrences 会把恰好等于平均值的记录误判为活跃。
  • 写成 HAVING COUNT(*) >= 1 会返回只在一种事件上超过平均值的业务 2。
  • 漏掉 ON a.event_type = e.event_type 会产生笛卡尔积，让一条记录与其他事件类型的平均值比较。
  • 使用 COUNT(DISTINCT business_id) 计数对象错误：分组内 business_id 本来就相同，应统计行数（即事件类型数）。
  • 对 AVG(occurrences) 取整会改变边界比较；例如平均值 7.5 时，出现次数 8 必须判为超过平均值。

相似题目

题目 难度 考察点
1107. 每日新用户统计 中等 同为「先聚合出中间表再统计」，中间量是每人首登日期而非分组平均值
184. 部门工资最高的员工 中等 分组取极值后回连明细，门槛是 MAX 且需要保留明细的多列
185. 部门工资前三高的所有员工 困难 从「超过门槛」升级到「组内前 N」，并列名次的处理是额外难点
182. 查找重复的电子邮箱 简单 只需单层分组 + HAVING COUNT(*) > 1，是本题最后一步的最小化练习
178. 分数排名 中等 需要为每行算出组级排名，最适合用窗口函数替代自连接
181. 超过经理收入的员工 简单 同样是「明细行与另一维度的值作比较」，只是基准来自自连接而非聚合