0004 - Median of Two Sorted Arrays

0004 - Median of Two Sorted Arrays

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)).

Examples

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

Input: nums1 = [0,0], nums2 = [0,0] Output: 0.00000

Input: nums1 = [], nums2 = [1] Output: 1.00000

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 Solution

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int median1 = 0;
        int median2 = 0;
        int index1 = 0;
        int index2 = 0;
        
        for(int i = 0; i <= (nums1.length + nums2.length) / 2; i++) {
            median1 = median2;
            if(index1 == nums1.length) {
                median2 = nums2[index2];
                index2++;
            }
            else if(index2 == nums2.length) {
                median2 = nums1[index1];
                index1++;
            }
            else if(nums1[index1] < nums2[index2]) {
                median2 = nums1[index1];
                index1++;
            }
            else {
                median2 = nums2[index2];
                index2++;
            }
        }
        
        if((nums1.length + nums2.length) % 2 == 0) return (float)(median1 + median2) / 2;
        return median2;
    }
}