Topic describes

Source: LeetCode

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.

Example 1:

Input: nums1 = [1,3], nums2 = [2]

Output: 2.00000

Merge array = [1,2,3], median 2

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]

Output: 2.50000

Merge array = [1,2,3,4], median (2 + 3) / 2 = 2.5

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]

Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]

Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []

Output: 2.00000

Tip:

• `nums1.length == m`
• `nums2.length == n`
• `0 <= m <= 1000`
• `0 <= n <= 1000`
• `1 <= m + n <= 2000`
• `-106 <= nums1[i], nums2[i] <= 106`

Advanced: Can you design a time complexity O(log (m+n)) algorithm to solve this problem?

Subject analysis

The general practice

If we merge the two arrays into a new array regardless of the order, and sort the new array, then take the values of (m+n)/ 2 and (m+n) -1/2, and average them. So you take the average regardless of whether the size of the resultant array is odd or even.

Merging two arrays is O(m+n), sorting the merged array is O(m+n) log(m+n)), and the whole thing is O(m+n) log(m+n)).

Binary search

Since the time required is order log(m+n), and the array is positively ordered, it is natural to use binary search. Since the number of elements to the left and right of the median is the same, m = nums1.length,n= nums2.length,k=m+n, then the number of elements to the left and right of the median is k/2. If nusM1 has I elements to the left of the median, So nums2 has j = k/2- I elements to the left of the median.

I and j divide the two arrays into left and right parts

• `nums1`The maximum left side of theta is going to be less than`nums2`The minimum on the right
• `nums2`The maximum on the left is less than`nums1`The minimum on the right

To satisfy this condition, we just need to change the size of I. For example, if we increase I, then j will decrease, nums1 will increase the maximum value on the left and nums2 will decrease the minimum value on the right

See the code and comments for details

``````public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
// The length of nums1 must not be greater than nums2, otherwise j may be less than 0
if (m > n) {
return findMedianSortedArrays(nums2, nums1);
}
// To use binary search, we need to remove half of the data at a time, because we want to change the value of I, so the value of I is in the interval [0,m],
// The first time I = m / 2, if the value of I is large, then the second interval becomes [0,m1], which is equal to the first I, and so on
int iMin = 0;
int iMax = m;
while (true) {
int i = (iMin + iMax) / 2;
int j = (m + n + 1) / 2 - i;
// If I is large, go left
if (i > iMin && nums1[i - 1] > nums2[j]) {
iMax = i - 1;
} else if (i < iMax && nums2[j - 1] > nums1[i]) {// if I is small, look right
iMin = i + 1;
} else {
// This boundary judgment is actually quite troublesome
// If there are an odd number of elements, then the median is the largest on the left
Math. Max (nums1[i-1], nums2[j-1])
// Obviously we can't use this formula when I and j are 0

int leftMax = 0;
int rightMin = 0;

if (i == 0) {
leftMax = nums2[j - 1];
} else if (j == 0) {
leftMax = nums1[i - 1];
} else {
leftMax = Math.max(nums1[i - 1], nums2[j - 1]);
}
if ((m + n) % 2= =1) {
return leftMax;
}

If there are an even number of elements
// rightMin = math.min (nums1[I], nums2[j])
// median = (leftMax + rightMin) / 2.0
// if I =m and j=n, rightMin is incorrect
if (i == m) {
rightMin = nums2[j];
}else if(j == n) {
rightMin = nums1[i];
}else {
rightMin = Math.min(nums1[i], nums2[j]);
}
if ((m + n) % 2= =0) {
return (leftMax + rightMin) / 2.0;
}
}
}
}
}
Copy the code``````

conclusion

The time complexity O(logm), because binary search is used, removes half of the data at a time, and only performs logm loops

The idea is to divide two arrays into four parts, two smaller parts to the left of the median and one larger part to the right of the median, but the code is a little tricky to write, mainly to determine the boundary values