Shawn's Blog
0%

4 Median of Two Sorted Arrays

Description

Given two sorted arrays nums1 and nums2 of size m and n respectively,
return the median of the two sorted arrays.

Example 1:

**Input:** nums1 = [1,3], nums2 = [2]
**Output:** 2.00000
**Explanation:** merged array = [1,2,3] and median is 2.

Example 2:

**Input:** nums1 = [1,2], nums2 = [3,4]
**Output:** 2.50000
**Explanation:** merged array = [1,2,3,4] and median is (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

Constraints:

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

Follow up: The overall run time complexity should be O(log (m+n)).

Solution 1: Merge Sort

Example

nums1 = {1,5,8,10,18,20}, nums2 = {2,3,6,7}

  • nums1: 1, 5, 8, 10, 18, 20
    i
  • nums2: 2, 3, 6, 7
    j

Time Complexity

Space Complexity

https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/1010562/Java-Easy-to-UnderStand-Solution-with-BinarySearch

Example

nums1 = {1,5,8,10,18,20}, nums2 = {2,3,6,7}, will be divided as

  • nums1: 1,5 || 8, 10, 18 , 20,
  • nums2: 2,3,6 || 7

l1 = 5, r1 = 8, l2 = 6, r2 = 7

Alreay known:

  • l1 > r1
  • l2 > r2

Binary search starting point

  • low = 0
  • high = n1

Binary seach on cut in nums1, transfer cut point in nums2

  • cut1 = (low + high) >> 1
  • cut2 = (cut1 + cut2 = (n1 + n2) / 2) => (n1 + n2) / 2 - cut1

cut to l1(l2), r1(r2)

  • l1 = cut1 - 1
  • r1 = cut1
  • l2 = cut2 - 1
  • r2 = cut2

Terminate condition:

  • l1 <= r2 && l2 <= r1

Time Complexity

Space Complexity