Как написать запрос для поиска медианы столбца в таблице в MySql?

Question

Я пытался решить проблему в Hackerrank SQL Раздел «Практика» и застрял в задаче «Проблема наблюдения за погодой 20».

Чтобы найти Медиану, я использовал следующий подход:

подзапрос для подсчета нижней половины записей. подзапрос для подсчета верхней половины записей. Приравняйте эти запросы вместе в предложении WHERE (чтобы запись имеет одинаковое количество записей до и после).

ЗАПРОС:

select round(s.lat_n,4) 
from station s 
where (
        select round(count(s.id)/2)-1 
        from station
    ) = (
        select count(s1.id) 
        from station s1 
        where s1.lat_n > s.lat_n
    );

ПОМОГИТЕ МНЕ С ОПТИМИЗИРОВАННЫМ ЗАПРОСОМ.

ССЫЛКА НА ПОЯСНЕНИЕ ПРОБЛЕМЫ: https://www.hackerrank.com/challenges/weather-observation-station-20/problem

Answer 1

Когда вы сортируете значения, медиана будет либо точно посередине (нечетное количество строк), либо средним из двух значений около середины (четное количество строк). Для этих значений верно следующее:

• не менее половины всех значений (включая его самого) равны или меньше
• не менее половины всех значений (включая его самого) равны или больше

Когда вы найдете эти / эти значения (назовем их кандидаты ), вам понадобится среднее значение различных значений-кандидатов.

Выше может быть выражается следующим запросом:

select round(avg(distinct lat_n), 4) as median_lat_n
from station s
cross join (select count(*) as total from station) t
where t.total <= 2 * (select count(*) from station s1 where s1.lat_n <= s.lat_n)
  and t.total <= 2 * (select count(*) from station s1 where s1.lat_n >= s.lat_n)

Обратите внимание, что это довольно медленное решение для больших таблиц.