订阅更新

锦标赛每组优胜者:别依赖子查询里的排序

SQL 实战 123 题 · 第 78 题 困难 约 3 分钟读完

LeetCode 1194 · 双向展开、分组取第一、非确定性写法

本文目录
  1. 面试怎么回答
  2. 题意
  3. 表结构
  4. 思路
  5. 参考解法
  6. 易错点

面试怎么回答

先把每场比赛按两个玩家展开成两行,UNION ALL 后按玩家汇总得分,再用 ROW_NUMBER() OVER (PARTITION BY group_id ORDER BY 总分 DESC, player_id) 取第一。我会特别指出:依赖子查询 ORDER BY 再 GROUP BY 取首行的写法不受标准保证,生产中要用窗口函数。

先把这段讲顺;面试官追问时,再展开下面的原理和细节。

详细讲解

题意

玩家表记录每个玩家所在的组,比赛表记录每场比赛的两个玩家和各自得分(同场两人同组)。每组得分总和最高的玩家获胜,分数相同时 ID 小的获胜。找出每组的获胜者。

表结构

  • Players:player_id(主键)、group_id
  • Matches:match_id(主键)、first_player、second_player、first_score、second_score

思路

一场比赛的两个玩家都要计分,所以先把比赛「展开」:第一名玩家和他的得分一行、第二名玩家和他的得分一行,UNION ALL 后按玩家汇总总分;再按组排名,取第一。原文的两种写法都依赖「子查询里先 ORDER BY,外层 GROUP BY 取每组第一行」,这是 MySQL 的未定义行为:新版本里优化器可能直接忽略子查询的排序,结果不可靠。

参考解法

select group_id, player_id
from (
    select players.*, sum(if(player_id = first_player, first_score, second_score)) score
    from players join matches
    on player_id = first_player or player_id = second_player
    group by player_id
    order by score desc, player_id
) tmp
group by group_id

另一种写法:窗口函数排名,结果确定,也照顾到没比赛的玩家

SELECT group_id, player_id
FROM (
  SELECT p.group_id, p.player_id,
         ROW_NUMBER() OVER (PARTITION BY p.group_id ORDER BY IFNULL(s.score, 0) DESC, p.player_id) AS rn
  FROM Players p
  LEFT JOIN (
    SELECT player, SUM(score) AS score FROM (
      SELECT first_player AS player, first_score AS score FROM Matches
      UNION ALL
      SELECT second_player, second_score FROM Matches
    ) x GROUP BY player
  ) s ON p.player_id = s.player
) t
WHERE rn = 1

易错点

  • 「子查询排序 + 外层 GROUP BY 取第一行」不受 SQL 标准保证,MySQL 5.7 以后可能被优化掉,换个版本结果就变了。
  • 没有参赛的玩家总分是 0,如果整组都没比赛,也应该有获胜者(ID 最小的)。
刷题进度保存在当前浏览器