04. Find the median of two positive arrays

#04. Find the median of two positive arrays

difficulty ： difficult

Given two sizes m and n Positive order of （ From small to large ） Array nums1 and nums2. Please find and return the median of these two positive arrays .

Advanced ： You can design a time complexity of O(log (m+n)) Does the algorithm solve this problem ？

Example 1：

Input ：nums1 = [1,3], nums2 = [2] Output ：2.00000 explain ： Merge array = [1,2,3] , Median 2 Example 2：

Input ：nums1 = [1,2], nums2 = [3,4] Output ：2.50000 explain ： 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

Tips ：

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

# violence

# Ideas

First, combine the two arrays into an array , Traversal

# Code

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        if (m == 0) {
            return getMid(nums2);
        }
        if (n == 0) {
            return getMid(nums1);
        }
        int[] temp = new int[m + n];
        int i = 0, j = 0, count = 0;
        while (count != (m + n)) {
            if (i == m) {
                while (j != n) {
                    temp[count++] = nums2[j++];
                }
                break;
            }
            if (j == n) {
                while (i != m) {
                    temp[count++] = nums1[i++];
                }
                break;
            }
            if (nums1[i] < nums2[j]) {
                temp[count++] = nums1[i++];
            } else {
                temp[count++] = nums2[j++];
            }
        }
        return getMid(temp);
    }

    public double getMid(int[] nums) {
        if (nums.length % 2 == 0) {
            return (nums[nums.length / 2] + nums[nums.length / 2 - 1]) / 2.0;
        } else {
            return nums[nums.length / 2];
        }
    }
}

Copy

# Dichotomy

To be added