Star

LeetCode 4. Median of Two Sorted Arrays

Posted on | In |

Question

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

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

The median is 2.0 

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

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

Explanation

既然题目要求用时间复杂度为O(log (m+n))的方法，很自然想到了二分法和分治法。中位数的表示可以用 (m + n +1)/2和(m + n + 2)/2这两个数除以2来表示。所以我们就要想办法找出两个未合并的数列中的第kth就好了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length; int n = nums2.length;
        int left = (m + n +1)/2; int right = (m + n + 2)/2;
        return (findKth(nums1, nums2, left) + findKth(nums1, nums2, right))/2.0;
    public int findKth(int[] nums1, int[] nums2, int k) {
        int m = nums1.length, n = nums2.length;
        // if m >n, change two arrays
        if (m > n) return findKth(nums2, nums1, k);
        // if any array is empty, just get the kth in second
        if (m == 0) return nums2[k-1];
        if (k == 1) return Math.min(nums1[0], nums2[0]);
        int i = Math.min(m, k/2);
        int j = Math.min(n, k/2);
        if (nums1[i-1] > nums2[j-1]) {
            return findKth(nums1, Arrays.copyOfRange(nums2, j, n), k-j);
        } else {
            return findKth(Arrays.copyOfRange(nums1, i, m), nums2, k-i);
        }
    }
}