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.

The time complexity of the algorithm should be order log 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

Source: LeetCode link: leetcode-cn.com/problems/me… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

  1. The basic idea

Use a boundary to divide two arrays into two equal parts. If there are odd numbers, make the left one more than the right, and then use the boundary value to find the median.

Even median = (maximum on the left + minimum on the right) / 2

The odd median is equal to the maximum on the left

  1. Special case handling
  • iorjIf there is no value on the left, the maximum value on the left isj-1ori-1The value at the position of

MaxLeft = B[J-1]

MaxLeft = A[i-1]

  • iorjThere is no value on the right-hand side, which is handled similarly
  1. iandjRelationship analysis of
  • For even numbers

i+j = (m+n)/2

  • For the odd case

i+j = (m+n+1)/2

  • merge

Since computers handle division of int types, adding 1 to the numerator of even numbers does not affect the result, so both odd and even numbers can be represented by the following relation:

i+j = (m+n+1)/2

So: j = (m+n+1)/ 2-1

  1. problem

Because knowing I will determine the position of j, the problem becomes simply finding the exact I. Because if you find I you can compute j, if you have I and j you can compute the maximum on the left and the minimum on the right, and then compute the median.

For the location of an I in an array, we can use dichotomy to find it, so the time complexity of this algorithm is O(log(min(m, n))).

  1. The whole process

algorithm

Public findMedianSortedArrays(int[] A, int[] B) {int m = a. length; int m = a. length; int n = B.length; if (m > n) { return findMedianSortedArrays(B, A); Int iMin = 0, iMax = m; While (iMin <= iMax) {// Use dichotomy for I, take the middle value of the interval int I = (iMin + iMax) / 2; int j = (m + n + 1) / 2 - i; // cross-check if the current I position is correct if (j! = 0 && i ! = m &&b [j-1] > A[I]) {// iMin = 1; } else if (i ! = 0 && j ! = n && A[i-1] > B[j]) { iMax = i - 1; } else {int maxLeft = 0; if (i == 0) { maxLeft = B[j - 1]; } else if (j == 0) { maxLeft = A[i - 1]; } else { maxLeft = Math.max(A[i - 1], B[j - 1]); If ((m + n) % 2 == 1) {return maxLeft; Int minRight = 0; // Int minRight = 0; if (i == m) { minRight = B[j]; } else if (j == n) { minRight = A[i]; } else { minRight = Math.min(B[j], A[i]); } return (maxLeft + minRight) / 2.0; }} to return 1.0; }Copy the code