Leetcode 4. Median of Two Sorted Arrays

[hard]

Median of Two Sorted Arrays - LeetCode

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

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

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
• -106 <= nums1[i], nums2[i] <= 106

[Java]

This problem ask time complexity be O(log(m+n)), but the solution is hard to understand. I will post a O(m+n) solution. It’s worse than optimal solution, but easier to understand and discuss.

1. know the total count for two arrays, and move from front to end until we meet the middle point.
2. 4 kind of situations, end of the array still not meet the middle point(array 1 and array 2), array1 number smaller than array2, than move array1 number forwarder.
3. if there is odd number, we can just return the number we stop; if there is even number, we should divid the number, and the answer need to change to float.