LeetCode:178.分数排名

题目链接:https://leetcode-cn.com/problems/rank-scores/

题目

编写一个 SQL 查询来实现分数排名。如果两个分数相同,则两个分数排名(Rank)相同。请注意,平分后的下一个名次应该是下一个连续的整数值。换句话说,名次之间不应该有“间隔”。

+----+-------+
| Id | Score |
+----+-------+
| 1 | 3.50 |
| 2 | 3.65 |
| 3 | 4.00 |
| 4 | 3.85 |
| 5 | 4.00 |
| 6 | 3.65 |
+----+-------+
例如,根据上述给定的 Scores 表,你的查询应该返回(按分数从高到低排列):

+-------+------+
| Score | Rank |
+-------+------+
| 4.00 | 1 |
| 4.00 | 1 |
| 3.85 | 2 |
| 3.65 | 3 |
| 3.65 | 3 |
| 3.50 | 4 |
+-------+------+

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/rank-scores
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

使用 oracle 或者 hive 的开窗函数,直接实现。

---- oracle ----
/* Write your PL/SQL query statement below */
select Score,
       dense_rank() over(order by Score desc) as Rank
from Scores; ---- 473ms

这么简单,不应该是中等难度的题目啊。。

不过 MySQL 中没有这种语法,学习一下应该如何实现?

学习一下大神的解法。

  • 如果通过子查询的方法来排序求行号,扫描成本 N*N
  • 使用 cross join 对一个行表进行关联,成本依旧很高
  • 使用 select @a := 0 产生只有一行的数据,扫描全表
---- MySQL ----
select score,
       @a := @a + 1 as rank
from scores,
     (select @a := 0) t
order by score desc;
-- 实现排序

针对相同的分数需要处理成相同的排名,所以需要添加辅助变量

@a := @a + (分数是否相同?0:1)
@a := @a + (@pre <> (@pre := score))

最终脚本,牛逼!

---- MySQL ----
select Score,
       @a := @a + (@pre <> (@pre := Score)) as rank
from Scores,
     (select @a := 0,
             @pre := -1) t
order by Score desc; ---- 138ms

解释一下:

  1. @a 类似在 Oracle 中的rownum,可以在生成结果内附加上一列序列号,可以近似理解为查询后加上行号;
  2. @a := @a + 1 实际上是赋值,旧值+1变为新值赋给@a
  3. 实际上并没有直接 @a+1 那么简单,还要先去判断分数是否与前一行相同,所以引入 @pre 来记录:
    • 先将Score赋值给: @pre := Score
    • 然后判断之前的 @pre 是否与赋值后的 @pre 不相同 ==> (@pre <> (@pre := Score)) “<>” 就是 "!=" 的意思;
    • 两者不同,判断结果为真,则取1; 两者相同,判断结果为假,取0, 最后再用 0或1 加上 @a 即为当前行分数的排名;
  4. (select @a := 0, @pre := -1) t 为初始化 @a@pre 的开始值;
    • @pre 初始值为 -1 为的是防止Score有 0 分的出现;
    • @第一次比较Score值的时候,@pre初始值肯定和Score不同, 所以第一次比较 @a 必然会 +1,所以@a要从0开始;
  5. 最后以将结果根据 Score 进行倒序展示;
  6. 顺便一提的是,这个代码的结果生成的rank带有小数点,可以考虑使用 cast() 方法来消除排名的小数点;

另一种,比较一般的解法。

---- MySQL ----
# Write your MySQL query statement below
select a.Score,
       (select count(distinct b.Score)
        from Scores b
        where b.Score > a.Score) + 1 as rank
from Scores a
order by Score desc;  ---- 605ms

自连接的解法速度比较慢。

思考

区分对比一下几个排序函数 row_number()rank()dense_rank()ntile() 的区别。

MySQL 中可以使用变量的方式进行求解。

上一篇:[数学] 方差和标准差


下一篇:1025.查询-from子句