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?
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.
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.
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.
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.
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.