preface

About the LeetCode array type problem related solutions, it can be seen that LeetCode array type problem before doing must see, classification solution summarized the problem, can be used to improve a single. If you think it is helpful, remember to give more likes and attention, thank you!

Topic describes

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

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

Answer key

  1. The brute force solution, which combines two ordered arrays together, calculates the number of digits based on the length of the combined array, and takes order n time.
/ * * *@param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}* /
var findMedianSortedArrays = function (nums1, nums2) {
  let nums = []
  let i = 0
  let j = 0
  let k = 0
  while (i < nums1.length && j < nums2.length) {
      if (nums1[i] < nums2[j]) {
          nums[k++] = nums1[i++]
      } else {
          nums[k++] = nums2[j++]
      }
  }
  // The nums1 array has remaining elements
  if(i < nums1.length) { nums.push(... nums1.slice(i)) }// The nusm2 array has remaining elements
  if(j < nums2.length) { nums.push(... nums2.slice(j)) }let res
  let len = nums.length
  if (len % 2) {
      res = nums[Math.floor(len / 2)]}else {
      res = (nums[len / 2] + nums[(len / 2) - 1]) * 0.5
  }
  return res 
Copy the code

2, use the properties of ordered array to find the median, in the LeetCode array type problem to do a must see the article, there is mentioned, if the question said ordered array, then should think of binary search, this problem can indeed use binary search to solve, the key is how to convert it into binary search problem. Let’s say we take the first number of M1 from nums1 and the first number of m2 from nums2. This number of M1 and m2 together form half of the number k after the combination of the two arrays. When the length of nums1 + nums2 is even, the median of the combined value is the average of the larger value of nums1[m1-1] and nums[m2-1] and the smaller value of nums1[m1] and nums2[m2], corresponding to the number at the positions of k-1 and k after the combination. When the length of nums1 + nums2 is odd, the combined median is the larger number in nums1[m1-1] and nums2[m2-1], corresponding to the combined number in the k-1 position. The specific analysis can be compared with the following figure:

(Note: Picture fromLeetcode flower sauce)

So once you have this idea, how do you find the corresponding m1, m2? M1 [m1] >= nums2[m2-1]; m1 [m1] >= nums2[m2-1] After finding M1, we can obtain the combined median by judging odd and even numbers and boundary conditions. The time complexity of this algorithm is O(logn) after binary search.

/ * * *@param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}* /
var findMedianSortedArrays = function (nums1, nums2) {
  const n1 = nums1.length;
  const n2 = nums2.length;
  if (n1 > n2) {
    return findMedianSortedArrays(nums2, nums1);
  }

  const k = Math.floor((n1 + n2 + 1) / 2); // Half of the array after the merge
  let l = 0;
  let r = n1;
  while (l < r) {
    const m1 = Math.floor((r - l) / 2) + l;
    const m2 = k - m1;
    if (nums1[m1] >= nums2[m2 - 1]) {
      r = m1;
    } else {
      l = m1 + 1; }}const m1 = l;
  const m2 = k - l;

  // The value at the k-1 position
  const c1 = Math.max(
    m1 <= 0 ? -Number.MAX_VALUE : nums1[m1 - 1], 
    m2 <= 0 ? -Number.MAX_VALUE : nums2[m2 - 1]);// The merged array is odd
  if ((n1 + n2) % 2= = =1) {
    return c1;
  }

  // The value at the k position
  const c2 = Math.min(
    m1 >= n1 ? Number.MAX_VALUE : nums1[m1],
    m2 >= n2 ? Number.MAX_VALUE : nums2[m2]
  );

  // The merged array is an even number
  return (c1 + c2) / 2;
};
Copy the code