This is the fourth day of my participation in Gwen Challenge

On day 4, we continue with problem 4. Although the level of this problem is difficult, but the amount of data given is only 1000, AC is not difficult in the past, but it is not easy to reach the advanced level.

The title

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 Explanation: Merge array = [1,2,3], median 2

Example 2: input: nums1 = [1,2], nums2 = [3,4] output: 2.50000 description: 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

Train of thought

So this is going to be the median, and if the total number is odd, it’s going to be the middle number. If it’s even, you have to take the average of the middle two numbers, which is also shown in example 2. Since these two arrays are ordered, we can use the method of interpolation sort to combine the two numbers into a large array, and then calculate the median. This idea is very clear, the time complexity is O(m+n), the space complexity is O(m+n). One optimization point is, because we’re interpolating and merging 2 ordered arrays, we actually only have to merge halfway to get the median, so we don’t have to do the merge, so the time is O((m+n)/2), which is really O(m+n), but since we don’t need to store the new merge array, the space is down to O(1).

Pay attention to

Note that in the interpolation process, one of the arrays has already been traversed, and also note that one of the arrays may be empty to begin with.

Java version code

class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int len1 = nums1.length; int len2 = nums2.length; int len = len1 + len2; If (len % 2 == 0) {// If (len % 2 == 0) {// If (len % 2 == 0) {// If (len % 2 == 0) { int start1 = 0; int start2 = 0; Int mmin = 0; while (index >= 0) { if (start1 < len1 && start2 < len2) { if (nums1[start1] < nums2[start2]) { if (index == 1) { mmin =  nums1[start1]; } else if (index == 0) { return avg(mmin, nums1[start1]); } start1++; } else { if (index == 1) { mmin = nums2[start2]; } else if (index == 0) { return avg(mmin, nums2[start2]); } start2++; } } else if (start1 < len1) { if (index == 1) { mmin = nums1[start1]; } else if (index == 0) { return avg(mmin, nums1[start1]); } start1++; } else { if (index == 1) { mmin = nums2[start2]; } else if (index == 0) { return avg(mmin, nums2[start2]); } start2++; } index--; }} else {// If the total length is odd, the number in the middle is the median int index = len / 2; int start1 = 0; int start2 = 0; while (index >= 0) { if (start1 < len1 && start2 < len2) { if (nums1[start1] < nums2[start2]) { if (index == 0) { return  nums1[start1]; } start1++; } else { if (index == 0) { return nums2[start2]; } start2++; } } else if (start1 < len1) { if (index == 0) { return nums1[start1]; } start1++; } else { if (index == 0) { return nums2[start2]; } start2++; } index--; } } return -1; } private static double avg(int a, int b) {return (a + b) / 2.0; }}Copy the code