锦标赛每组优胜者:别依赖子查询里的排序
LeetCode 1194 · 双向展开、分组取第一、非确定性写法
面试怎么回答
先把每场比赛按两个玩家展开成两行,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 最小的)。