use definition of median

  • 0

    Use the definition of median:
    if a number n is median, then

    So I left join the numbers table with itself first to get the frequency(smaller_than_n), then I join it with the total frequency. Therefore, frequency(larger_than_n)=total-frequency(n)-(frequency_smaller_than_n) and we can use the definition.

    Finally, select the average of the result set as the result can be 1 or 2 records.

    select avg(temp.number) as median
       (select n1.number, 
               ifnull(sum(n2.frequency),0) as sm_frequency,
         from numbers n1 
         left join numbers n2 on n1.number>n2.number,
         (select sum(frequency) as total from numbers n3) tt
             group by n1.number 
             having abs(total-sm_frequency*2-frequency)<=n1.frequency) temp

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.