Formatted question description: https://leetcode.ca/all/4.html

4. Median of Two Sorted Arrays

Level

Hard

Description

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

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

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution

Use the idea of binary search. First of all, if nums1.length > nums2.length, then swap the two arrays nums1 and nums2.

Next, search in the shorter array nums1 to make the algorithm more efficient. Initially let low be 0 and high be nums1.length. Each time set index1 = (high - low) / 2 + low, and let index2 = (nums1.length + nums2.length + 1) / 2 - index1. If nums1[index1] < nums2[index2 - 1], then set low = index1 + 1. If nums1[index1 - 1] > nums2[index2], then set high = index1 - 1. Otherwise, if the sum of the two arrays’ lengths is odd, then the median is either nums1[index1 - 1] or nums2[index2 - 1]. If the sum of the two arrays’ lengths is even, then the other element that determines the median is either nums1[index1] or nums[index2]. Calculate the median accordingly.

Why is it ““target/2”” ??? For example, [1,3,5,…,99], [2,4,6,…,100] two cases

  1. A total of 100 numbers, then the 50th in all sorts. The average number from the two arrays is 25 numbers each
  2. If it is not average, then [1,2,3,…,50], [51,52,…,100] are all taken from the first array, that is, the first 25 must be From the first array

case m is much longer than n midIndex/2 to check private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {

Pitfalls

  1. The k in dfs is the number of several, not the index. But start/end is index
  2. leftMedian and rightMedian are also numbers, not index int leftMedian = (m + n + 1) / 2; int rightMedian = (m + n + 2) / 2;
  3. dfs termination condition k==1 if (k == 1) { return Math.min(nums1[start1], nums2[start2]); }

solution-2: The optimal solution O(log min(m,n)), a short array of binary search

Code

Java

public class Median_of_Two_Sorted_Arrays {


    // time: O(log(m,n))
    // space: O(1)
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int m = nums1.length;
            int n = nums2.length;
            int leftMedian = (n + m + 1) / 2;
            int rightMedian = (n + m + 2) / 2;

            return (getKth(nums1, 0, m - 1, nums2, 0, n - 1, leftMedian) + getKth(nums1, 0, m - 1, nums2, 0, n - 1, rightMedian)) * 0.5;
        }

        private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
            int len1 = end1 - start1 + 1;
            int len2 = end2 - start2 + 1;

            if (len1 > len2) {
                return getKth(nums2, start2, end2, nums1, start1, end1, k);
            }
            if (len1 == 0) {
                return nums2[start2 + k - 1];
            }

            if (k == 1) {
                return Math.min(nums1[start1], nums2[start2]);
            }

            int i = start1 + Math.min(len1, k / 2) - 1;
            int j = start2 + Math.min(len2, k / 2) - 1;

            if (nums1[i] > nums2[j]) {
                return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
            } else {
                return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
            }
        }
    }


    // good ref, with no array copy
    // https://www.geeksforgeeks.org/median-two-sorted-arrays-different-sizes-ologminn-m/

    // ref: https://leetcode.com/articles/median-of-two-sorted-arrays/
    /*
        Time complexity: O(log(min(m,n))).
        At first, the searching range is [0, m].
        And the length of this searching range will be reduced by half after each loop.
        So, we only need log(m) loops.
        Since we do constant operations in each loop, so the time complexity is O(log(m)).
        Since m <= nm≤n, so the time complexity is O(log(min(m,n))).

        Space complexity: O(1)O(1).
        We only need constant memory to store 99 local variables, so the space complexity is O(1).
     */
    // time: O(log min(m,n))
    // space: O(1)
    class Solution_iteration {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int length1 = nums1.length, length2 = nums2.length;
            if (length1 > length2) {
                int[] tempArray = nums1;
                nums1 = nums2;
                nums2 = tempArray;
                int temp = length1;
                length1 = length2;
                length2 = temp;
            }
            int low = 0, high = length1, halfLength = (length1 + length2 + 1) / 2;
            while (low <= high) {
                int index1 = (high - low) / 2 + low;
                int index2 = halfLength - index1;
                if (index1 < high && nums1[index1] < nums2[index2 - 1])
                    low = index1 + 1;
                else if (index1 > low && nums1[index1 - 1] > nums2[index2])
                    high = index1 - 1;
                else {
                    int maxLeft = index1 == 0 ? nums2[index2 - 1] : index2 == 0 ? nums1[index1 - 1] : Math.max(nums1[index1 - 1], nums2[index2 - 1]);
                    if ((length1 + length2) % 2 == 1)
                        return maxLeft;
                    int minRight = index1 == length1 ? nums2[index2] : index2 == length2 ? nums1[index1] : Math.min(nums1[index1], nums2[index2]);
                    return (maxLeft + minRight) / 2.0;
                }
            }
            return 0.0;
        }
    }



	public class Solution2_bruteForce {

	    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
	        if(nums1 == null || nums2 == null) {
	            return -10000;
	        }

	        int totalLength = nums1.length + nums2.length;
	        int mid = totalLength / 2;

	        if (totalLength % 2 == 1) {
	            return findTarget(nums1, nums2, mid);
	        } else {
	            return (findTarget(nums1, nums2, mid) + findTarget(nums1, nums2, mid - 1)) / 2;
	        }
	    }

	    // brute force, counting. O(m+n)
	    public double findTarget(int[] nums1, int[] nums2, int targetIndex) {

	        int p1 = 0;
	        int p2 = 0;

	        while(p1 < nums1.length || p2 < nums2.length) {

	            if(p1 + p2 == targetIndex) {
	                int v1updated = p1 < nums1.length ? nums1[p1] : Integer.MAX_VALUE;
	                int v2updated = p2 < nums2.length ? nums2[p2] : Integer.MAX_VALUE;

	                return Math.min(v1updated, v2updated);
	            }

	            int v1 = p1 < nums1.length ? nums1[p1] : Integer.MAX_VALUE;
	            int v2 = p2 < nums2.length ? nums2[p2] : Integer.MAX_VALUE;

	            if(v1 < v2) {
	                p1++;

	            } else {
	                p2++;
	            }
	        }

	        return -10000; // or throw exception "result not found"
	    }
	}

}

All Problems

All Solutions