This is the first article I participated in beginners’ introduction.

preface

Finding the median of two positive ordinal groups

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 2Copy the code

Example 2:

Input: nums1 = [1,2], nums2 = [3,4] output: 2.50000 description: merge array = [1,2,3,4], median (2 + 3) / 2 = 2.5Copy the code

Example 3:

Input: nums1 = [0,0], nums2 = [0,0] output: 0.00000Copy the code

1. How to solve the problem

The median is the number in the middle of an ordered set of data. In this case, finding the median of two positive Ordinal Numbers can be interpreted as combining two arrays to find the median. The solution is as follows:

  • Use merge method, merge two ordered array, get a large ordered array. The middle element of a large ordered array is the median.

  • Instead of merging two ordered arrays, just find the location of the median. Since the lengths of the two arrays are known, the sum of the subscripts corresponding to the median is also known. Maintain two Pointers, starting at the subscript 00 of each array, moving the pointer to the smaller value back one bit at a time (if one pointer has reached the end of the array, you only need to move the pointer to the other array) until you reach the median.

Two, code implementation

Method 1: Merge arrays by force

Ideas:

Merge two arrays directly using JS’s concat() method and sort them using sort()

Code:

var findMedianSortedArrays = function (nums1, nums2) {
    let temp = nums1.concat(nums2).sort((a, b) => {
        return a - b;
    });
    if (temp.length % 2 !== 0) {
        return temp[(temp.length - 1) / 2];
    } else {
        return (temp[temp.length / 2] + temp[(temp.length / 2) - 1]) / 2;
    }
};
Copy the code

Results:

Method two: binary search

Ideas:

By definition, the median is the average of the (m+n)/2 elements in two ordered arrays when m+n is odd and the average of the (m+n)/2 elements and (m+n)/2+1 elements in two ordered arrays when m+n is even. So this problem can be converted to finding the KTH smallest number in two ordered arrays, where k is (m+n)/2 or (m+n)/2+1.

Code:

Var findMedianSortedArrays = function(nums1, nums2) {if (nums1.length > nums2.length) {if (nums1.length > nums2.length) { nums2] = [nums2, nums1]; } let m = nums1.length; let n = nums2.length; Let left = 0; let right = m; // median2: let median1 = 0; let median2 = 0; While (left <= right) {// The former part contains nums1[0.. i-1] and nums2[0.. j-1] // the latter part contains nums1[I.. m-1] and nums2[j.. n-1] const I =  left + Math.floor((right - left) / 2); const j = Math.floor((m + n + 1) / 2) - i; const maxLeft1 = i === 0 ? -Infinity : nums1[i - 1]; const minRight1 = i === m ? Infinity : nums1[i]; const maxLeft2 = j === 0 ? -Infinity : nums2[j - 1]; const minRight2 = j === n ? Infinity : nums2[j]; if (maxLeft1 <= minRight2) { median1 = Math.max(maxLeft1, maxLeft2); median2 = Math.min(minRight1, minRight2); left = i + 1; } else{ right = i - 1; } } return (m + n) % 2 == 0 ? (median1 + median2) / 2 : median1; };Copy the code

Time complexity O(log(min(m, n))), where n is the length of NUMs1 and m is the length of NUMs2

Results:

Third, summary

The problem itself is not difficult, and can be easily implemented using brute force methods, but the difficulty is that the problem limits the time complexity O(log (m+n)), so it is easy to think of using binary search to solve the problem. This problem is really examining the algorithm and its time complexity.