Java - O(n+m) - Merging the two arrays


  • 0
    G

    This is a simple solution which is O(n+m) time and O(n+m) space.
    Given that the two arrays are already sorted, we could use the merge sort logic to merge the two arrays into one.
    Then its simply the case of picking up the center element (or two if the array size is even).

    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int n1 = nums1.length;
            int n2 = nums2.length;
            int m = n1 + n2;
            int[] merged = new int[m];
            int i=0, j=0;
            while(i < n1 || j < n2) {
                int a = i < n1 ? nums1[i] : Integer.MAX_VALUE;
                int b = j < n2 ? nums2[j] : Integer.MAX_VALUE;
                merged[i+j] = (i < n1 && a < b) ? nums1[i++] : nums2[j++];
            }
            return (m&1) == 0 ? (merged[m/2-1] + merged[m/2])/2.0 : merged[m/2];
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.