LeetCode 4.

Question

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

Example 1:

Input: nums1 = [1,3], nums2 = [2]

Output: 2.0
Example 2:

Input: [1,2], nums2 = [3,4]

Output: 2.5

Complexity

Time complexity: O(log(m+n))
Space complexity: O(1)

Code

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int left = 0, right = 0;
        double result = 0;
        if ((nums1.length + nums2.length) % 2 == 0) {
            int mid2 = (nums1.length+nums2.length)/2;
            int mid1 = mid2 - 1;
            boolean isMid1 = false, isMid2 = false;
            while (left < nums1.length && right < nums2.length) {
                if (left + right == mid1) {
                    result += nums1[left] <= nums2[right] ? nums1[left] : nums2[right];
                    isMid1 = true;
                }else if (left + right == mid2) {
                    result += nums1[left] <= nums2[right] ? nums1[left] : nums2[right];
                    isMid2 = true;
                    break;
                }

                if (nums1[left] <= nums2[right]) {
                    left++;
                }else{
                    right++;
                }
            }

            if (!isMid1 && !isMid2) {
                int pos1 = left == nums1.length ? mid1 - left : mid1 - right;
                int pos2 = pos1 + 1;
                result += left == nums1.length ? nums2[pos1] : nums1[pos1];
                result += left == nums1.length ? nums2[pos2] : nums1[pos2];
            }else if (isMid1 && !isMid2) {
                int pos2 = left == nums1.length ? mid2 - left : mid2 - right;
                result += left == nums1.length ? nums2[pos2] : nums1[pos2];
            }
            return result /= 2;
        }else{
            int mid = (nums1.length + nums2.length) / 2;
            while (left < nums1.length && right < nums2.length) {
                if (left + right == mid) return nums1[left] <= nums2[right] ? nums1[left] : nums2[right];

                if (nums1[left] <= nums2[right]) {
                    left++;
                }else{
                    right++;
                }
            }
            int pos = left == nums1.length ? mid - left : mid - right;
            return left == nums1.length ? nums2[pos]: nums1[pos];
        }
    }
}

Check out the description of this problem at LC 4.