首页 > 试题广场 >

最差是第几名(二)

[编程题]最差是第几名(二)
  • 热度指数：58645 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
TM小哥和FH小妹在牛客大学若干年后成立了牛客SQL班，班的每个人的综合成绩用A,B,C,D,E表示，90分以上都是A，80~90分都是B，70~80分为C，60~70为D，E为60分以下
假设每个名次最多1个人，比如有2个A，那么必定有1个A是第1名，有1个A是第2名(综合成绩同分也会按照某一门的成绩分先后)。
每次SQL考试完之后，老师会将班级成绩表展示给同学看。
现在有班级成绩表(class_grade)如下:
grade number
A 2
C 4
B 4
D 2
第1行表示成绩为A的学生有2个
.......
最后1行表示成绩为D的学生有2个

老师想知道学生们综合成绩的中位数是什么档位，请你写SQL帮忙查询一下，如果只有1个中位数，输出1个，如果有2个中位数，按grade升序输出，以上例子查询结果如下:
grade
B
C
解析:
总体学生成绩排序如下:A, A, B, B, B, B, C, C, C, C, D, D，总共12个数，取中间的2个，取6，7为:B,C


示例1

输入

drop table if exists class_grade;
CREATE TABLE class_grade (
grade varchar(32) NOT NULL,
number int(4) NOT NULL
);

INSERT INTO class_grade VALUES
('A',2),
('C',4),
('B',4),
('D',2);

输出

B
C
算法知识视频讲解
添加回答
Mysql
牛客861030304号头像 牛客861030304号 
select grade from
    (select 
         grade,
         number,
         sum(number) over (order by grade)+0.5 n2,
         (sum(number) over() +1)/2 z_n 
     from class_grade) t
where z_n>=(n2-number) and z_n<=n2;
有点偏的写法

发表于 2021-12-29 15:38:23 回复(0)
SunburstRun头像 SunburstRun
首先我们需要知道:当某一数的正序和逆序累计均大于整个序列的数字个数的一半即为中位数
比如:
A A B B C C D D 
1 2 3  4  5 6  7 8
8 7 6  5  4  3 2 1
那么上面的4，5以及5，4就是中位数，如果是奇数的话，就只有1个
再比如
A2个，B3个，C5个，D2个，
正序2，5，10，12
倒序12，10，7，2
正序和12，大于等于6的为C，D，
逆序和12，大于等于6的为A，B，C，所以最后中位数为C


根据(一)https://blog.nowcoder.net/n/60f8ed8d360c4307a8875349caf22b77 我们知道求正序和的写法，
求逆序和其实就是 sum(a) over (order by b desc) 就行了，多加了一个desc，那么我们可以写出如下代码: 

 select grade,(select sum(number) from class_grade) as total,              
    sum(number) over(order by grade) a,              
    sum(number) over(order by grade desc) b           
 from class_grade order by grade;
得到中间表的结果如下:

将 a>=total的一半并且 b>=total的一半列出，就得到了最后需要的结果: 
select grade from (select grade,(select sum(number) from class_grade) as total,
        sum(number) over(order by grade) a,
        sum(number) over(order by grade desc) b
        from class_grade) t1
where a >= total/2 and b >=total/2
order by grade;
编辑于 2021-04-27 14:35:49 回复(25)
刘凯201904072208786头像 刘凯201904072208786

思路

  1. 首先求出每个等级的开始名次left_order和结束名次right_order。
  2. 然后求出中位数所在名次mid。
  3. 如果mid在某个等级的开始名次left_order和结束名次right_order之间，则输出该等级。

步骤

1. 求出每个等级的开始名次和结束名次

结束名次比较好算，直接用窗口函数对number求和sum(number) over(order by grade)，开始名次在这个基础上减去number再-1即可。

select grade
      ,number
      ,sum(number) over(order by grade)-number+1 as left_order
      ,sum(number) over(order by grade)          as right_order
  from class_grade
 order by grade

图片说明

2. 求出中位数所在的名次

中位数的公式是(起始名次+最终名次)/2，起始名次是1，最终名次就是对所有的number求和sum(number)，考虑到有时候中位数是1个，有时候是2个，利用向左取整floor和向右取整ceil并用union去重得到中位数。

select floor((sum(number)+1)/2) as mid
  from class_grade
union 
select ceil((sum(number)+1)/2) as mid
  from class_grade

得到mid为6和7

3. 找到中位数对应的等级

直接用mid between介于开始名次left_order和结束名词right_order之间就能找到对应的等级。
注意中位数可能有两个，恰好在同一个等级里面，所以这里要加上distinct关键词去重。
最终代码如下：

-- 第1张表
with t1 as 
(
select grade
      ,number
      ,sum(number) over(order by grade)-number+1 as left_order
      ,sum(number) over(order by grade)          as right_order
  from class_grade
 order by grade
)
-- 第2张表
, t2 as 
(
select floor((sum(number)+1)/2) as mid
  from class_grade
union 
select ceil((sum(number)+1)/2) as mid
  from class_grade
)
-- 3. 找到中位数对应的等级
select distinct grade
  from t1,t2
 where t2.mid between left_order and right_order

最终grade输出B和C。

发表于 2021-05-08 16:24:57 回复(2)
Linken94头像 Linken94
可能是最简单的解法 
select grade from
    (select *, (tb1.ed - tb1.number) st, sum(number) over() tp from    
         (select *, sum(number) over(order by grade) ed from class_grade) tb1
    ) tb2
where tp/2 between st and ed;

发表于 2021-03-11 16:15:42 回复(21)
林冲吃牛肉头像 林冲吃牛肉

解法一(select * from SunburstRun) 

select grade from 
(
    select grade, (select sum(number) from class_grade) as total,
        sum(number) over(order by grade) a,
        sum(number) over(order by grade desc) b
        from class_grade
) t1
where a >= total/2 and b >=total/2
order by grade;

正逆向数为总数一半的数为中位数，总数为奇数时中位数只有一个，为偶数时中位数有两个。

解法二

如果找到每个 grade 的排名范围 α，那么 α 中如果包含中位数，那么 α 对应的 grade 即为所求。
用例 
drop table if exists class_grade;
CREATE TABLE class_grade (
grade varchar(32) NOT NULL,
number int(4) NOT NULL
);

INSERT INTO class_grade VALUES
('A',2),
('D',1),
('C',2),
('B',2);
sql: 
-- lag('列名', 前 N 行, 超出行数时默认设置值, 没设置为 null): 取前 N 行
-- lead('列名', 后 N 行, 超出行数时默认设置值, 没设置为 null): 取后 N 行
with t1 as (
    -- 结果为 4
    -- 偶数时为左边的中位数
    select round(sum(number) / 2, 0) mid from class_grade
    union
    -- 偶数时为右边的中位数 
    -- 奇数时的中位数
    select round((sum(number) + 1) / 2, 0) mid from class_grade
),
t2 as (
  -- grade|number|right_order
  --  A|2|2
  --  B|2|4           
  --  C|2|6           
  --  D|1|7
    select grade, number, 
        sum(number) over(order by grade) right_order from class_grade
),
t3 as (
  -- grade|number|left_order|right_order
  -- A|2|0|2
  -- B|2|3|4
  -- C|2|5|6
  -- D|1|7|7
    select grade, number, 
    (lag(right_order, 1,0) over() + 1) as left_order, right_order from t2
)
select distinct grade from t3, t1 
    where t1.mid between left_order and right_order;

解法三 

-- 第1张表
with t1 as
(
select grade
      ,number
      ,sum(number) over(order by grade)-number+1 as left_order
      ,sum(number) over(order by grade)          as right_order
  from class_grade
 order by grade
)
-- 第2张表
, t2 as
(
select floor((sum(number)+1)/2) as mid
  from class_grade
union
select ceil((sum(number)+1)/2) as mid
  from class_grade
)
-- 3. 找到中位数对应的等级
select distinct grade
  from t1,t2
 where t2.mid between left_order and right_order


编辑于 2021-05-26 18:44:20 回复(1)
牛客626904108号头像 牛客626904108号 
select grade
from
(select grade,
 sum(number) over(order by grade) as a,
 sum(number) over(order by grade desc) as b,
 (select sum(number) from class_grade) as cnt
from class_grade)t
where a>=cnt/2 and b>=cnt/2
order by grade

发表于 2021-03-11 20:13:42 回复(1)
牛客900219936号头像 牛客900219936号
搞了一种非常简单粗暴的算法（我太笨了所以只想出来了最笨的方法）
首先，选出每个等级的名次范围以及两个中位数（奇数的话两个中位数是一样的，偶数的话就相差1）
比如说A有两个，那对应的等级范围就是1到2；总计七位学生，两个中位数就都是4： 
select *,sum(number) over(order by grade) e,sum(number) over(order by grade)-number+1 s
from class_grade,(
	select (case when sum(number)%2=0 then round(sum(number)/2,0)
        else round((sum(number)+1)/2,0) end) start,(case when sum(number)%2=0 then round(sum(number)/2+1,0)
        else round((sum(number)+1)/2,0) end) end
	from class_grade) b
然后判断两个中位数是否在某个等级的名次范围内；
总数为7的情况下就是判断4在哪个等级的范围内，总数为8的话就是判断4和5在哪个等级范围内（可能是两个可能是一个），最后的代码： 
select a.grade
from (
select *,sum(number) over(order by grade) e,sum(number) over(order by grade)-number+1 s
from class_grade,(
	select (case when sum(number)%2=0 then round(sum(number)/2,0)
        else round((sum(number)+1)/2,0) end) start,(case when sum(number)%2=0 then round(sum(number)/2+1,0)
        else round((sum(number)+1)/2,0) end) end
	from class_grade) b) a
where start between s and e&nbs***bsp;end between s and e;


发表于 2021-04-08 16:52:14 回复(0)
牛客130211310号头像 牛客130211310号
改进了一点讨论一 的写法,算total sum的时候如果直接用sum会改变行数, 但sum(number) over()就不会了, 就不需要再select sum了
select grade from (select grade,sum(number) over() as total,
        sum(number) over(order by grade) a,
        sum(number) over(order by grade desc) b
        from class_grade) t1
where a >= total/2 and b >=total/2
order by grade;
发表于 2021-10-10 13:15:35 回复(1)
Mysql
笛卡尔的笛笛头像 笛卡尔的笛笛
with t1 as 
(
select grade,sum(number) over (order by grade) aggregate
from class_grade
),
t2 as
(
select floor((sum(number)+1)/2) m1,ceil((sum(number)+1)/2) m2
from class_grade
)

select min(t1.grade)
from t1,t2
where t1.aggregate>=t2.m1
union
select min(t1.grade)
from t1,t2
where t1.aggregate>=t2.m2
发表于 2022-06-16 16:08:03 回复(0)
Stzolo头像 Stzolo
#解题思路
1.利用窗口函数求出累加值
2.累加值-number+1就是该等级的起点位置
3.求中值在哪个等级的区间范围内 
select a.grade
from (select grade,
      (select ROUND(sum(number)/2, 0) from class_grade) as  t_min,
      (select ROUND((sum(number)+1)/2, 0) from class_grade) as t_max from class_grade) a 
join (SELECT *, sum(number) over(order by grade) as t_con FROM class_grade) b
on a.grade = b.grade
where (t_min BETWEEN t_con-b.number+1 and  t_con) or (t_max BETWEEN  t_con-b.number+1 and t_con)
order by a.grade

发表于 2022-04-20 16:58:48 回复(2)
Mysql
我叫谢小盟，叫我查尔斯好了头像 我叫谢小盟，叫我查尔斯好了 
##4
##开窗函数
##当某一数的正序和逆序累计均大于整个序列的数字个数的一半即为中位数(不考虑频率)

SELECT grade

FROM 

(SELECT grade,
        SUM(number)OVER(ORDER BY grade DESC) AS r1,
        SUM(number)OVER(ORDER BY grade ASC) AS r2,
        (SELECT SUM(number) FROM class_grade) AS total
 FROM class_grade) AS t1
 
WHERE r1 >= total/2
AND r2 >= total/2
ORDER BY grade

发表于 2021-10-23 18:29:03 回复(0)
Mysql
xl_lunxlu头像 xl_lunxlu 
select grade
from 
(
    select grade
    ,sum(number)over(order by grade desc) sm
    ,sum(number)over(order by grade ) sm2
    ,sum(number)over() sm_all
    from class_grade
) t 
where t.sm>=t.sm_all/2 and t.sm2>=t.sm_all/2

发表于 2021-10-09 15:58:43 回复(1)
牛客260016156号头像 牛客260016156号
抄的
select c.grade from (select 
grade , 
sum(number) over (order by grade) sum1,
sum(number) over (order by grade desc) sum2,
(select sum(number) from class_grade) as sum3

from class_grade) c
where c.sum1 >= c.sum3/2
and c.sum2 >= c.sum3/2
order by c.grade
发表于 2021-04-19 16:27:23 回复(0)
anisso头像 anisso
看了一下评论区“SunburstRun”的解答，确实很巧妙，但是一开始想不到这种思路，这里提供一个新思路，也是我看到本题的第一个想法：
    本题的表提供的是按grade分组聚合后的结果，但是目标却是整体数据求中位数，那么我们可不可以将数据展开还原呢？
我的想法是根据number列的最大值m新建一个临时表numbers，它只有一列n，值为1-m；将class_grade表和numbers按照class_grade.number>=numbers.n的条件进行合并，那么可以得到新表 new_grade如下：
grade number n
A 2 1
A 2 2
C 4 1
C 4 2
C 4 3
C 4 4
B 4 1
B 4 2
B 4 3
B 4 4
D 2 1
D 2 2
然后对新表new_grade通过开窗函数row_number() 根据grade列分别进行升序和降序排列，如下：
grade number n rank1 rank2
A 2 1 1 12
A 2 2 2 11
B 4 1 3 10
B 4 2 4 9
B 4 3 5 8
B 4 4 6 7
C 4 1 7 6
C 4 2 8 5
C 4 3 9 4
C 4 4 10 3
D 2 1 11 2
D 2 2 12 1
现在只需要挑选表中rank1=rank2 或 abs(rank1-rank2)=1的数据行即可。

发表于 2021-03-22 15:23:25 回复(5)
牛客421553514号头像 牛客421553514号 
select grade from
    (select *, lag(number1, 1,0) over() as number2 from 
            (select *, sum(number) over(order by grade) number1 ,
                    (select round(sum(number)/2,0)from class_grade) s1,
                    (select round((sum(number)+1)/2,0)from class_grade) s2
                    from class_grade) s) s3
where (number2 < s1 and number1 >= s1)
or (number2 < s2 and number1 >= s2)
分享一个利用lead函数和lag函数的思路
编辑于 2021-03-15 14:54:57 回复(2)
橙子24头像 橙子24
评论里这个方法不对吧，比如：
A：2
B：7
C：3
D：4
按照评论里的这段代码，那么这里的中位数就是B和C，但是很显然，事实上中位数应该是B 
select 
grade 
from 
(
    select grade
    ,(select sum(number) from class_grade) as total
    ,sum(number) over(order by grade) a
    ,sum(number) over(order by grade desc) b
    from class_grade
) t1
where a >= total/2 
and b >=total/2
order by grade;

发表于 2024-08-15 17:59:07 回复(2)
Mysql
Sunny_G头像 Sunny_G

哈哈，一个笨方法吧，中位数最多有两个，那么久直接把两个都找出来，然后去重就好了，注意排序哦

select *
from (
    select grade 
    from (
        select grade, sum(number) over(order by grade) as rn
        from class_grade
    ) t
    where rn >= (
        select floor((sum(number)+1)/2)
        from class_grade
    )
    order by grade asc 
    limit 1
) t
union 
select *
from (
    select grade 
    from (
        select grade, sum(number) over(order by grade) as rn
        from class_grade
    ) t
    where rn >= (
        select ceil((sum(number)+1)/2)
        from class_grade
    )
    order by grade asc 
    limit 1
) t
发表于 2024-08-14 18:08:17 回复(0)
Mysql
牛客533436893号头像 牛客533436893号
不使用窗口函数
select cg.grade
from class_grade cg
where (
    select sum(`number`)
    from class_grade
    where grade < cg.grade
) <=(
    select sum(`number`) / 2
    from class_grade
) -- 中位数大于等级左边界
and (
    select sum(`number`)
    from class_grade
    where grade <= cg.grade
) >= (
    select sum(`number`) / 2
    from class_grade
) -- 中位数小于等级右边界
order by cg.grade
编辑于 2023-12-09 20:43:20 回复(0)
牛客563312411号头像 牛客563312411号
当某一数的正序和逆序累计均大于或等于整个序列的数字个数的一半即为中位数 
select grade 
from (select grade,
      (select sum(number) from class_grade) total,
      sum(number)over(order by grade) r1,
      sum(number)over(order by grade desc) r2 
      from class_grade) a
where r1>=total/2 and r2>=total/2
order by 1


发表于 2023-11-03 19:15:18 回复(0)
Mysql
4fbd81e头像 4fbd81e 
# 新建2列，总人数，前缀和
with t1 as (
    select *,
    sum(number) over(order by grade asc) as cumsum,
    sum(number) over() as total_num
    from class_grade
)

# 如果该grade【最好位次和最差位次区间】包括了【人数/2】
SELECT
  grade
FROM t1
WHERE cumsum - number <= total_num / 2 # 注意这里只能这么写，其他3种<(=)   >(=)  的组合不管用
AND cumsum >= total_num / 2;

发表于 2023-03-24 09:20:01 回复(0)
提交观点

问题信息

上传者：牛客301499号
难度：
181条回答 2854浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最差是第几名(二)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号