use definition of median


  • 0
    Z

    Use the definition of median:
    if a number n is median, then
    frequency(n)>=abs(frequency(larger_than_n)-frequency(smaller_than_n)).

    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
        from
       (select n1.number, 
               n1.frequency, 
               ifnull(sum(n2.frequency),0) as sm_frequency,
               tt.total
         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.