[LeetCode] 4. Median of Two Sorted Arrays

Posted on | In

Problem

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:

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

The median is 2.0

Example 2:

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

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

Explanation

  1. No matter the length of the array is odd or even, the median is always be $((length+1)/2 + (length+2)/2)/2.0$. So, we need to find the $(length+1)/2$ number between these two arrays and the $(length+2)/2$ number between these two arrays, then divide by 2.0.

    1
    2
    3
    4
     [1, 2, 3, 4] the median is 2.5
 (4+1)/2=2 as integer
 (4+2)/2=3 as integer
 (2+3)/2.0=2.5 as double

  2. To find the kth number between two sorted array, we can divide the k in half. Then check if the kHalf number in array1 is bigger or smaller than the kHalf number in array2.

    • If the kHalf number in array1 is smaller, then it means the kth number is not in the first kHalf number in array1, then we recusivly find the k-KHalf number this time between these two arrays, but this time array1 starts from kHalf+1, which is the start index.
      • And if one of the array’s length is less than their start index, then we simply return the kth number in another array.
      • And if k is 1, we can simply check both array’s first element. The one smaller is the k number.
      • And if one of the array doesn’t have the kHalf number, which means the kth number is not in another array.
    1
    2
    3
    4
    5
    6
     arr1: [1, 3, 5, 7]
 arr2: [2, 4, 6, 8]
 (8+1)/2=4=k
 (8+2)/2=5=k
 (4+5)/2=4.5
 Median is 4.5

    We give one example when k = 4, kHalf = 2.

    In arr1, the kHalf number is 3; in arr2, the kHalf number is 4; Because 3 < 4, the Kth number is in arr2. Then, we ignore the first kHalf number in arr1, and check arr1 starts from kHalf+1. In other words now we check [5, 7] and [2, 4, 6, 8].

    Now we find the k number which is 4-2=2, kHalf now is 2/2=1.

    Compare the kHalf number between these two arrays, we see that 2 from arr2 is smaller than 5 from arr1, we know that the kth number is not in the kHalf number in array 2. Now we compare [5, 7] and [4, 6, 8] with the k qual to k-kHalf=2-1=1. Now the k=1, we can simply check the first element of these two arrays. The one smaller is the k number. In this case is 4.

    Finally, we conclude that the between arr1[1, 3, 5, 7] and arr2[2, 4, 6, 8] the k=4th number is 4.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int left = (m + n + 1) / 2, right = (m + n + 2) / 2;
        int a = findKth(nums1, 0, nums2, 0, left);
        int b = findKth(nums1, 0, nums2, 0, right);
        return (a+b)/2.0;
    }
    int findKth(int[] nums1, int i, int[] nums2, int j, int k) {
        if (i >= nums1.length) return nums2[j + k - 1];
        if (j >= nums2.length) return nums1[i + k - 1];
        if (k == 1) return Math.min(nums1[i], nums2[j]);
        int kHalf = k/2;
        int midVal1=(i+kHalf-1 < nums1.length)? nums1[i+kHalf-1]: Integer.MAX_VALUE;
        int midVal2=(j+kHalf-1 < nums2.length)? nums2[j+kHalf-1]: Integer.MAX_VALUE;
        if (midVal1 < midVal2) {
            return findKth(nums1, i+kHalf, nums2, j, k-kHalf);
        } else {
            return findKth(nums1, i, nums2, j+kHalf, k-kHalf);
        }
    }
}