This is the fourth day of my participation in the August More text Challenge. For details, see:August is more challenging

The title

Given two positively ordered (from small to large) arrays nums1 and nums2 of size m and n, respectively. Find and return the median of these two 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 explanation: 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

 

Tip:

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

 

Advanced: Can you design an algorithm of order log (m+n) to solve this problem?

Their thinking

So let’s start with the concept of Median. Median in an array is the Median that divides the array into left and right equal parts.

The diagram below:

This problem, it’s easy to think of a violent solution, the time complexity and the space complexity are both O(m+n), which does not meet the time complexity requirement of O(log m+n). We can start with a simple solution, try it out, and violent solutions are also accepted by Leetcode. In the analysis, there are two solutions, the brute force solution and the dichotomy solution.

1. Brute Force

Merge two sorted arrays (A, B) into one sorted array.

I’m going to do two Pointers (I, j), where I starts at A, where I equals 0, and j starts at B, where j equals 0. A[I] and B[J],

  1. ifA[i] <= B[j], then theA[i]I’m going to put it in a new array, and I’m going to move I back one bit, which isi+1.
  2. ifA[i] > B[j], then theB[j]I’m going to put it in the new array, and I’m going to move j back one bit, which isj+1.
  3. Repeat steps #1 and #2 untiliMove to theAFinally, orjMove to theBAt last.
  4. ifjMove to theBArray last, so just take the rest of theAPut them in the new array.
  5. ifiMove to theAArray last, so just take the rest of theBPut them in the new array.

The following figure shows the Merge process.

Time complexity:O(m+n) \- m is length of A, n is length of B

Space complexity:O(m+n)

Binary Search

Since the arrays in question are sorted, it’s easy to think of Binary Search when you’re looking in an sorted array, so I’m going to do A Binary Search for the smaller part of the array, so I’m going to make sure that A and B are partitioned

Len (Aleft)+len(Bleft)=(m+n+1)/2 \ -m is the length of array A, n is the length of array B

Partition on array A at the interval [0,m]

As shown in figure:

The following figure shows some examples of different situations (note that when there are no elements on the left or right, the left is usedINF_MINThe right to useINF_MAXRepresents left and right elements:

The following figure shows an example of how to solve the partition problem.

Time complexity: O(log(min(m, n)) \ -m is length of A, n is length of B

Space complexity: O(1) – There is no extra space here

Idea 3

  1. Merge the two arrays and then call the array’s sort method to sort in ascending order
  2. Divide the length of the new array by 2, round it down, and assign it to mid
  3. If the length of the new array is odd, return arr[mid]; if it is even, return (arr[mid] + arr[mid-1]) / 2

Key point analysis

  1. Merge two sorted numbers into an array in linear time.
  2. Binary search, the key thing is

  • For A partition to form two equal parts, len(Aleft)+len(Bleft)=(m+n+1)/2 \ -m is the length of array A and n is the length of array B

  • (maxLeftA), (minRightA), (maxLeftB), (maxLeftB) MaxLeftA <= minRightB && maxLeftB <= minRightA)

So with these two conditions, so median is one of these four numbers, depending on whether it’s odd or even,

Odd: median = Max (maxLeftA, maxLeftB) even: median = (Max (maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2

code

Idea 1

/ * * *@param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}* /
var findMedianSortedArrays = function(nums1, nums2) {
  // Merge sort
  const merged = []
  let i = 0
  let j = 0
  while(i < nums1.length && j < nums2.length) {
    if (nums1[i] < nums2[j]) {
      merged.push(nums1[i++])
    } else {
      merged.push(nums2[j++])
    }
  }
  while(i < nums1.length) {
    merged.push(nums1[i++])
  }
  while(j < nums2.length) {
    merged.push(nums2[j++])
  }

  const { length } = merged
  return length % 2= = =1
    ? merged[Math.floor(length / 2)]
    : (merged[length / 2] + merged[length / 2 - 1) /2
};
Copy the code

Complexity analysis

  • Time complexity: O(Max (m,n))O(Max (m,n))O(Max (m,n))
  • Space complexity: O(m+n)O(m +n)O(m +n)

Idea 2

/** * Binary solution *@param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}* /
var findMedianSortedArrays = function(nums1, nums2) {
  // make sure to do binary search for shorten array
  if (nums1.length > nums2.length) {
    [nums1, nums2] = [nums2, nums1]
  }
  const m = nums1.length
  const n = nums2.length
  let low = 0
  let high = m
  while(low <= high) {
    const i = low + Math.floor((high - low) / 2)
    const j = Math.floor((m + n + 1) / 2) - i

    const maxLeftA = i === 0 ? -Infinity : nums1[i-1]
    const minRightA = i === m ? Infinity : nums1[i]
    const maxLeftB = j === 0 ? -Infinity : nums2[j-1]
    const minRightB = j === n ? Infinity : nums2[j]

    if (maxLeftA <= minRightB && minRightA >= maxLeftB) {
      return (m + n) % 2= = =1
        ? Math.max(maxLeftA, maxLeftB)
        : (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2
    } else if (maxLeftA > minRightB) {
      high = i - 1
    } else {
      low = low + 1}}};Copy the code

Complexity analysis

  • Time complexity: O (log (min (m, n))) O (log (min (m, n))) O (log (min (m, n)))
  • The space complexity: O (log (min (m, n))) O (log (min (m, n))) O (log (min (m, n)))

Idea 3

/ * * *@param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}* /
var findMedianSortedArrays = function (nums1, nums2) {
  const arr = [...nums1, ...nums2];
  // return arr.reduce((acc, cur) => acc + cur) / arr.length;
  const mid = Math.floor(arr.sort((a, b) = > a - b).length / 2);
  if (arr.length % 2= = =1) {
    return arr[mid];
  }
  return (arr[mid] + arr[mid - 1) /2;
};
Copy the code

The last

I dreamed of going all over the world with a sword

Take a look at the prosperity of the world

Young hearts are always a little frivolous

Just a man after all

No regrets I go my way

“Front brush” No.4