This is the sixth day of my participation in Gwen Challenge

This article has participated in the weekend study program, click to see more details

Find the median of two positive ordinal groups

Given two positive-ordered (from small to large) arrays of size m and n, nums1 and nums2. Please find and return the median of the two positive ordinal groups.

Thought analysis

The easiest way to do this is to merge and decide whether to use index N /2 based on the sum of the array lengths or whether to add index N /2 and n/2 + 1 and divide by 2.

The time of this method is order n.

You also need to create a large array in space.

So is there a better way?

If you know how to solve the problem, you can draw the target with the arrow.

  • Two ordered arrays, the median is a number, and if the sum of the array lengths is odd, that is the sum of the number in the middle of the array array, and if the sum of the array lengths is even, that is the sum of the left and right of the array array array.

  • For an array of length 8, size=7, then the median is the number indexed 7/2 and 7/2 + 1,

  • For an array of length 7, size=6, then the median index is 6/2 =3 numbers

  • We can find a size/2 line, the left side of the line must be size/2-1 (because the line itself is one)

  • Since there are two arrays, it is likely that the array does not have a median, so change the definition of the line to the number on the left: size/2-1. (There is a sense of SQL self-join sort)

  • So if the first array A has x lines to the left, the second array B has y=size/2-1-x lines to the left.

  • That is [0, the size / 2-1], [1, the size / 2-2], [2, the size / 2-3],… ,[m – 1,size/2 – m]

  • So the time complexity is reduced to the smaller m of the two arrays.

So how to analyze whether this line is reasonable

It’s really simple as long as the maximum on the left of the line is less than the minimum on the right of the line

max(arr[i],arr1[j]) < min(arr[i + 1] , arr1[j + 1])
Copy the code

I’m going to end up doing a little bit of analysis here, and all I have to do is look at the analysis of boundary conditions, and write a few more if things