Problem description

Two ordered arraysnums1 和 nums2, their array lengths are m and n respectively. Find the median of the two arrays, and the overall time complexity must be.

Assume that nums1 and nums2 are not null.

Case 1:

Nums1 = [1, 3] nums2 = [2] median is 2.0Copy the code

Example 2:

Nums1 = [1, 2] Nums2 = [3, 4] The median value is (2 + 3)/2 = 2.5Copy the code

Problem of the difficulty

Hard

Their thinking

So the way you do the first pass, the way you do the first pass, is you walk through the two queues in order from smallest to largest, all the way toThat’s the median we want, and we thought, well, that’s too easy,HardSo much for the rank.

And if you look at it more closely, it also has a time complexity of zero, while the time complexity of my scheme is, does not satisfy the problem condition. It can be seen that this condition alone is validHardLevel.

The key to solving this problem is not a brilliant algorithm, but to have a picture in mind that looks like this:

left side | right side nums1: A(0),A(1),... ,A(i-1) | A(i),... ,A(m-1) nums2: B(0),B(1),... ,B(j-1) | B(j),... ,B(n-1)Copy the code

If we view the two arrays as a whole, with a vertical line separating the elements in the middle, and the elements on the left are the same as those on the right (if the total number is odd, the left side has 1 more element than the right side), then whenIf is even, the median iswhenWhen is odd, the median is

We all know that the left-hand side is zero, and the elements on the left and right sides are the same, then


We can write j in terms of I, then


So, the problem becomes, look for an I in array A so thatAnd,That’s true. The implication of these two inequalities is that the smallest number to the right of the vertical line must not be less than the largest number to the left, and if that’s true, we can say that we’ve found this vertical line.

When we’re looking for I, we’re going to run into itTheta, at which point we need to move I to the right, thetaIncreases, as I moves to the right, j decreases as I increases, i.eDelta is going to get smaller, so that after I, it’s going to get us closer to our goal; Similarly, whenPhi, we need to move I to the left.

Through the above analysis, we can finally use the binary search method to find the I value, and since the time complexity of binary search isThis method can meet the requirements of the question.

The boundary conditions for this problem are as follows: since j is calculated by subtracting I, and I is at most m (when A is all on the left), in order for j not to be negative, array A needs to be the one with the fewer elements.

When I is 0, all of A is on the right-hand side, so we just have to figure outSet up; When I is m, all of A is on the left, so we just have to figure outSet up

Similarly, when j is 0, B is all on the right-hand side, so we just have to figure outSet up; When j is n, B is all on the left-hand sideCan be

So, we can write the following code:

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        m, n = len(nums1), len(nums2)
        if m > n:
            m, n, nums1, nums2 = n, m, nums2, nums1

        if m == 0 and n == 0:
            return None

        begin = 0
        end = m
        i = j = 0
        while True:
            i = (begin + end) / 2
            j = (m + n + 1) / 2 - i

            if (i == 0 or j == n or nums2[j] >= nums1[i- 1]) and\
                    (i == m or j == 0 or nums1[i] >= nums2[j- 1]):
                left_max = 0
                if i == 0: left_max = nums2[j- 1]
                elif j == 0: left_max = nums1[i- 1]
                else: left_max = max(nums1[i- 1],nums2[j- 1])
                
                if (m+n)%2! =0:
                    return left_max

                right_min = 0
                if i == m: right_min = nums2[j]
                elif j == n: right_min = nums1[i]
                else: right_min = min(nums1[i], nums2[j])

                return (left_max + right_min)*1.0/2

            elif j < n and i > 0 and nums2[j] < nums1[i- 1]:
                end = i - 1
            elif j > 0 and i < n and nums1[i] < nums2[j- 1]:
                begin = i + 1
Copy the code

This problem is difficult to understand directly by looking at the code, but if you have the above picture in mind, you can slowly solve the problem along the way, so it is not easy to achieve the requirements of the problem.

The original link