This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

Source: LeetCode

Link: leetcode-cn.com/problems/me…

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

  • nums1The maximum left side of theta is going to be less thannums2The minimum on the right
  • nums2The maximum on the left is less thannums1The 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