4. Median of Two Sorted Arrays

LeetCode

If the length of the sum of two arrays is even, the median indexes are len / 2 - 1 and len / 2. Otherwise, the median index is len / 2.

Solution Alpha

// Time Complexity: O(m + n)
// Space Complexity: O(1)
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int len = m + n;
        int left = 0, right = 0;
        int ptr1 = 0, ptr2 = 0;
        for (int i = 0; i <= len / 2; i++) {
            left = right;
            if (ptr1 < m && (ptr2 >= n || nums1[ptr1] < nums2[ptr2])) {
                right = nums1[ptr1];
                ptr1++;
            } else {
                right = nums2[ptr2];
                ptr2++;
            }
        }
        if (len % 2 == 0) {
            return (left + right) / 2.0;
        } else {
            return right;
        }
    }
}

Solution Beta

// TODO: solve this problem in time complexity of O(log(m + n))