This is the 21st day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Find the median of two positive ordinal groups

Hot100 4. Find the median of two positive ordinal groups

Difficulty: difficulty

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

Given two positive-ordered (from small to large) arrays of size m and n, num1 and num2. Please find and return the median of the two positive ordinal groups.

The algorithm should be order log of m plus n.

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

Example 4:

Input: nums1 = [], nums2 = [1] Output: 1.00000Copy the code

Example 5:

Input: nums1 = [2], nums2 = [] Output: 2.00000Copy the code

Tip:

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

Answer key

Law – violent law

This method does not meet the requirements of the problem, but Leetcode can A.

Merge two sorted arrays, use two Pointers to each array, by comparing the size of the value into the new array, if one array loop ends, the remaining value of the other array into the new array.

/ * * *@param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}* /
var findMedianSortedArrays = function(nums1, nums2) {
  const mergeArr = [];
  let i = 0, j = 0;
  while(i < nums1.length && j < nums2.length){
    if(nums1[i] > nums2[j]) {
      mergeArr.push(nums2[j++])
    }else{
      mergeArr.push(nums1[i++])
    }
  }
  while(i < nums1.length) {
    mergeArr.push(nums1[i++]);
  }
  while(j < nums2.length) {
    mergeArr.push(nums2[j++]);
  }
  
  const len = mergeArr.length;
  return len % 2= = =1 ? mergeArr[Math.floor(len / 2)] : (mergeArr[len / 2] + mergeArr[len / 2 - 1) /2;
}
Copy the code

Time complexity: O(m+ N)

Space complexity: O(m+ N)

Method 2 binary search

Since both arrays are in positive order, it’s easy to figure out how to use binary lookup.

Divide two arrays (A, B) conditionally until the condition is satisfied:

  • Length of leftA + length of leftB = (sum of two array lengths + 1) / 2
  • A maximum left (maxLeftA), A minimum right (minRightA), B maximum left (maxLeftB), B minimum right (minRightB) satisfy:(maxLeftA <= minRightB && maxLeftB <= minRightA)

Median is in these four numbers, and data can be processed according to odd or even numbers.

/** * binary solution *@param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}* /
​
var findMedianSortedArrays = function(nums1, nums2) {
  if(nums1.length > nums2.length) {
    [nums1, nums2] = [nums2, nums1];
  }
  const m = nums1.length, n = nums2.length;
  let low = 0, high = m;
  while(low <= high) {
    const i = low + Math.floor((high - low) / 2);
    const j = Math.floor((m + n + 1) / 2) - i;
    
    const maxLeftNums1 = i === 0 ? -Infinity : nums1[i - 1];
    const minRightNums1 = i === m ? Infinity : nums1[i];
    
    const maxLeftNums2 = j === 0 ? -Infinity : nums2[j - 1];
    const minRightNums2 = j === n ? Infinity : nums2[j];
    
    if(maxLeftNums1 <= minRightNums2 && minRightNums1 >= maxLeftNums2) {
      return (m + n) % 2= = =1 
        ? Math.max(maxLeftNums1, maxLeftNums2)
        : (Math.max(maxLeftNums1, maxLeftNums2) + Math.min(minRightNums1,minRightNums2)) / 2
    } else if(maxLeftNums1 > minRightNums2) {
      high = i - 1;
    } else {
      low = low + 1; }}}Copy the code

O(log(min(m,n)))

Space complexity: O(log(min(m,n))

Practice every day! Front end small sprout new one, hope can point to like + look at wow ~