What does median mean?


  • 10
    Y
    Input:	[1,1], [1,2]
    Expected:	1.00000
    
    Input:	[4,5,6,8,9], []
    Expected:	6.00000
    
    Input:	[], [2,3]
    Expected:	2.50000
    

    I don't understand!

    What does median mean?

    What on earth should I do?

    Can anyone help me?


  • 39
    S

    median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

    Examples:

    • [2,3,4] , the median is 3

    • [2,3], the median is (2 + 3) / 2 = 2.5

    For this problem, what you should do is find the median after merging this two ordered array.


  • 0
    Y

    Thanks! I know it.


  • 0
    R

    yes, I think this problem should definitely say the median after merging two array.


  • 6
    G

    According to the question, this problem should be solved without merging the two sorted arrays. The cost of merging would be O(m+n) and so then you don't have a solution with O(log(m*n)) or O(log m + log n) .

    One possible solution can be found here, but I strongly encourage you to try it yourself before you check the solution.


  • 0
    U

    According to the author of the linked page, the complexity is O(LogM + LogN), which is actually O(Log(M*N)). It is more complex than the required O(Log(M+N)) complexity.
    The only way I can think of to solve the problem is merging. It is obvious that we can not simply merge the two arrays COMPLETELY, which is also not necessary to find the MEDIAN.


  • 0
    G

    You are correct, it should be * instead of +. My Bad!


  • 0
    D

    why more complex ?
    logm+logn = log(mn) <= log( (m + n) ^ 2) =2 log(m + n) = O(log(m + n))


  • 0
    D

    Best explanation can be found here: kth smallest element in two sorted arrays.
    Remember that median is (m+n+1)/2 smallest element in two arrays.


  • 0
    Z

    for large int m,n : m+n < mn, so log(m+n) < log(mn) = log(m) +log(n)


  • 0
    D

    why my proof is wrong ?


  • 0
    Y

    because you were comparing different concepts. Think this way, log(m+n) >= logm and log(m+n) >= logn. So 2log(m+n) >= logm + logn. Of course you can't just multiply a constant in this case. Because from complexity pov, they are the same.


  • 0
    O

    You need to compare them as: (m+n)^2 = m^2 +n^2 +2*mn. Or, according to your proof, the log(n^4) = 4log(n)=O(log(n)), there are two variables, one treats n^4 as n, one treats n as n. as Yefei said, two concepts.


  • 0
    I

    i can't see why I should do the merge?


  • 0
    E

    Just want you know. You're right about this. O(log(mn)) = O(log(m+n)). Because: there exist k = 2 and m0 = n0 = 1. For any m > m0 and n > n0, there is log(mn) <= k*log(m + n).


  • 0
    Q

    Tell the truth I still don't understand quite clear the requirement, it said that those 2 arrays respectively and people always provide the solution to get the middle item of the combined/merged array is (m+n)/2 (depend of odd or even number). However, I see the test cases have a case like [1,1] and [1,2], so what is the merged array: [1,1,2] or [1,2] or [1,1,1,2]. I think it should be [1,1,2] for the end result is 1.0. Then the merged array will have 3 items. So what is the rule for the merged array? For ex: [1,3,5,7] and [3,4,5,7,8,9], the merged one should be [1,3,4,5,7,8,9]? Then the total item of the merged array is 7 but not m + n = 4 + 6, so the median should be 5. Then the problematic should be the merging algorithm.


Log in to reply
 

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