Topic information

Source address: Find the median of two positive arrays

Give two positively ordered (from small to large) arrays nums1 and nums2 of sizes m and n, respectively. Please find out and return the median of these two positive arrays.

The time complexity of the algorithm should be \ (O(log (m+n)) \).

Prompt information

Example 1

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
 Explanation: merge arrays = [1,2,3] ，Median 2

Example 2

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
 Explanation: merge arrays = [1,2,3,4] ，median (2 + 3) / 2 = 2.5

Tips

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -10^6 <= nums1[i], nums2[i] <= 10^6

Implementation logic

Merging method

The first way to solve the problem is to combine two ordered arrays into an ordered array, and then calculate the median of the result set. This method is a relatively direct idea.

However, merging two arrays is the most time-consuming operation of this method, and it reaches the time complexity of \ (O(m+n) \), so it does not meet the requirement that the time complexity of the algorithm in the topic reaches \ (O(log (m+n)) \).

Moreover, the space complexity of this method has reached the level of \ (O(m+n) \), and its space occupation is not optimal.

package cn.fatedeity.algorithm.leetcode;

public class MedianOfTwoSortedArrays {
    public double answer(int[] nums1, int[] nums2) {
        int i = 0, j = 0;
        int[] numbers = new int[nums1.length + nums2.length];
        int index = 0;
        while (i < nums1.length || j < nums2.length) {
            if (i == nums1.length) {
                for (int k = j; k < nums2.length; k++) {
                    numbers[index++] = nums2[k];
                }
                break;
            } else if (j == nums2.length) {
                for (int k = i; k < nums1.length; k++) {
                    numbers[index++] = nums1[k];
                }
                break;
            }

            if (nums1[i] < nums2[j]) {
                numbers[index++] = nums1[i++];
            } else if (nums2[j] < nums1[i]) {
                numbers[index++] = nums2[j++];
            } else {
                numbers[index++] = nums1[i++];
                numbers[index++] = nums2[j++];
            }
        }
        if ((numbers.length & 1) == 0) {
            // Array length is even
            int mid = numbers.length >> 1;
            return (numbers[mid - 1] + numbers[mid]) / 2f;
        } else {
            return numbers[numbers.length >> 1];
        }
    }
}

Double pointer

Facing two arrays, you can also use double pointers, as long as you find the position of the median. Since the length of the two arrays is known, the sum of the subscripts of the two arrays corresponding to the median is also known.

The basic idea is to filter the smaller values in the two arrays one by one through double pointers until they reach the subscript position of the median, and then the median of the two arrays can be obtained.

The whole method is better than the merging method, and the spatial complexity is directly reduced to the degree of \ (O(1) \). In terms of running efficiency, it only cycles \ (\frac{m+n}2\) times, but the time complexity is still \ (O(m+n) \, which does not meet the requirements of \ (O(log (m+n)) \) in the title.

package cn.fatedeity.algorithm.leetcode;

public class MedianOfTwoSortedArrays {
    public double answer(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int len = m + n;
        int mStart = 0, nStart = 0;
        int left = 0, right = 0;
        for (int i = 0; i <= len >> 1; i++) {
            left = right;
            if (mStart < m && (nStart >= n || nums1[mStart] < nums2[nStart])) {
                right = nums1[mStart++];
            } else {
                right = nums2[nStart++];
            }
        }
        if ((len & 1) == 0) {
            return (left + right) / 2f;
        } else {
            return right;
        }
    }
}

Binary search

Generally, most of the problems requiring a time complexity of \ (O(log (n)) \) can be solved using the idea of dichotomy.

This topic can also use dichotomy to make the time complexity meet the requirements of \ (O(log (m+n)) \), but it is indeed a dichotomy search with a little anti thinking logic.

The main idea of solving the problem is to determine the selected value of \ (\frac{1}{2}\) through the combined length, compare the \ (\frac{1}{2}\) value in the two arrays, filter the smaller part directly until \ (\frac{m+n}{2}\) value is filtered, and the remaining first index of the two arrays is used to calculate the median.

package cn.fatedeity.algorithm.leetcode;

public class MedianOfTwoSortedArrays {
    public double answer(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int total = len1 + len2;
        int left = (total + 1) >> 1;
        int right = (total + 2) >> 1;
        if (left == right) {
            return this.findK(nums1, 0, nums2, 0, left);
        } else {
            return (this.findK(nums1, 0, nums2, 0, left) + this.findK(nums1, 0, nums2, 0, right)) / 2.0;
        }
    }

    private int findK(int[] nums1, int i, int[] nums2, int j, int k) {
        if (i >= nums1.length) {
            // num1 has been filtered out
            return nums2[j + k - 1];
        } else if (j >= nums2.length) {
            // num2 has been filtered
            return nums1[i + k - 1];
        }
        if (k == 1) {
            // First numeric comparison in array
            return Math.min(nums1[i], nums2[j]);
        }

        // Determine the two values to compare each time
        int mid1 = (i + (k >> 1) - 1) < nums1.length ? nums1[i + (k >> 1) - 1] : Integer.MAX_VALUE;
        int mid2 = (j + (k >> 1) - 1) < nums2.length ? nums2[j + (k >> 1) - 1] : Integer.MAX_VALUE;

        if (mid1 < mid2) {
            return findK(nums1, i + (k >> 1), nums2, j, k - (k >> 1));
        } else {
            return findK(nums1, i, nums2, j + (k >> 1), k - (k >> 1));
        }
    }
}