4. Median of Two Sorted Array

发表于 | 分类于

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

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

解法1： Math

参考这篇解释
C++

1

Java

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int m = nums1.length;
            int n = nums2.length;
            if (m > n) {
                return findMedianSortedArrays(nums2, nums1);
            }
            int start = 0, end = m, half = (m + n + 1) / 2;
            // Satisfy both condition, calculate the medium
            int max_of_left = 0, min_of_right = 0, i = 0, j = 0;
            while (start <= end) {
                i = (start + end) / 2;
                j = half- i;
                if (i < m && j > 0 && nums2[j - 1] > nums1[i]) {
                    start = i + 1;
                } else if (i > 0 && j < n && nums1[i - 1] > nums2[j]) {
                    end = i - 1;
                } else {
                    if (i == 0) {
                        max_of_left = nums2[j - 1];
                    }
                    else if (j == 0) {
                        max_of_left = nums1[i - 1];
                    } else {
                        max_of_left = Math.max(nums1[i - 1], nums2[j - 1]);
                    }
                    break;
                }
            }
           // Check if the total number of elements is odd or even
            if ((m + n) % 2 == 1) {
                return max_of_left;
            }
            if (i == m) {
                min_of_right = nums2[j];
            } else if (j == n) {
                min_of_right = nums1[i];
            } else {
                min_of_right = Math.min(nums1[i], nums2[j]);
            }
            return (max_of_left + min_of_right)/2.0;
        }
}

解法2： Kth Value

这个解法比较好理解一点，也不容易错，要考虑的edge case容易一些。
基本的思想就是先要写出一个find kth element in a two sorted array的function。
这个function可以用递归的方式实现，而每一次递归，两个array都需要去掉当中一个的一半。
想法就是：
如果第一个array的长度是0，那么第k个一定在第二个array的k-1位置。
如果k==1，那么第k个就是当前比较的array的第一个的最小值
如果都不是，那么可以把两个array都砍两半。假设是A和B。
比较A和B的中点，一个是pa = k/2，另一个就是k - pa， 为的是保证左右两半都是k个数。
然后比较这两个数，如果mA < mB，则说明前pa个数都不是第k个数的备选，可以抛掉。相反同理
如果ma == mB，则说明已经找到第k个数，返回即可。

等kth function写出来之后，就可以按照总长度是奇数还是偶数。
如果是奇数，就直接求total / 2的数，
如果是偶徐，需要把中间两个数的平均数返回。
总的时间复杂度是O(logM + logN) = O(logMN)

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
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int total = m + n;
        if (total % 2 == 0) {
            return (findKth(nums1, 0, nums2, 0, total / 2) + findKth(nums1, 0, nums2, 0, total / 2 + 1)) / 2.0;
        } else {
            return findKth(nums1, 0, nums2, 0, total / 2 + 1);
        }
    }
    private double findKth(int[] nums1, int i, int[] nums2, int j, int k) {
        int len1 = nums1.length - i;
        int len2 = nums2.length - j;
        if (len1 > len2) {
            return findKth(nums2, j, nums1, i, k);
        }
        if (len1 == 0) return nums2[j + k - 1];
        if (k == 1) return Math.min(nums1[i], nums2[j]);
        int pa = Math.min(len1, k / 2);
        int pb = k - pa;
        if (nums1[i + pa - 1] < nums2[j + pb - 1]) {
            return findKth(nums1, i + pa, nums2, j, k - pa);
        } else if (nums1[i + pa - 1] > nums2[j + pb - 1]) {
            return findKth(nums1, i, nums2, j + pb, k - pb);
        } else {
            return nums1[i + pa - 1];
        }
    }
}