4. Median of Two Sorted Arrays

[yunshuipiao]

4. Median of Two Sorted Arrays

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

题解

这题难度为 hard， 我思考了一天做不出来，因此参考了star 数目最高的答案， 下面就贴一下该解法， 学习其思想，还要考虑各种边界条件。kotlin 代码见 _0004.kt 文件。解法如下：

---

为了解决这个问题，首先需要明白中位数是什么概念：一组数据分为两组，其中一组总是比另一组小。

Wiki：对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个，则中位数不唯一，通常取最中间的两个数值的平均数作为中位数。

针对此题来说，用随机的 i 将 A 分为两部分，注意 i 的位置；

  left_A（i 个）          |        right_A （m - i 个）
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]

因为 A 有 m 个元素，因此一共有 m + 1 中分割的方法。当 i = 0， 左边为空；

B 也是一样分割方法：

 left_B                  |        right_B
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

此时将两个部分合并在一起：

  left_part              |        right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

此时思考，怎么找到满足题解的答案：

既然求中位数，因此只需要确认：

1.len(left_part) == len(left_right)
2.max(left_part) <= min(left_right)

两个条件，就可以把 A，B 分为长度相等两部分，此时 median = (max(left_part) + min(left_right))/2

上述就是针对中位数作出的分析。

详细步骤

为了确认上述两个条件，只需要确认：

1. i + j = m - i + n - j, 可以得到 i，j 的关系
  所以 i = 0～m， j = (m + n) / 2 - i (n >= m)
2 A[i - 1] <= B[j] && B[j - 1] <= A[i]: 保证左边始终比右边小

这里解释一下为什么需要 n >= m, 因为在算式中，j = (m + n) / 2 - i 可能会取到负值，导致结果错误；

上述的 A[i-1],B[j-1],A[i],B[j] 即使在 i=0/i=m/j=0/j=n 条件下也成立，后续解释。

因此问题就变为二分查找：

在 [0, m] 找到满足条件的 i， 使得 B[j - 1] <= A[i] && A[i - 1] <= B[j], (j =(m + n) / 2 - i )

步骤如下：

1. low =0， high = m, 在[low, high] 中进行查找。
2. 令 i = low + (high - low) / 2, j = (m + n)  / 2 - i;
3. 这时，肯定满足 len(left) == len(right)， 此时会遇到三种情况：
   - B[j - 1] <= A[i] && A[i - 1] <= B[j], 这就是需要找的情况；
   - B[j - i] > A[i] ,说明左边还存在数大于右边， i 需要增加，使得 B[j - 1] <= A[i];
     Low = i + 1
   - A[i - 1] >= B[j]， 同样说明说明左边还存在数大于右边， 需要减小 A[i - 1] 的值来满足条件， i 需要减小；
     high = i - 1
4. 更新完 low, high， 继续进行二分查找；

当需要的 i 值找到， 中位数即可得出：

1. 当 （m + n ）% 2 == 1 : median =( max(B[j - 1], A[i - 1]) + min(B[j], A[i]) )/ 2
2. 当 （m + n ）% 2 == 0: median = min(A[i], B[j])。

举个例子：

当 A = [1, 2, 3 ,4], B = [2, 3], 时，i = 2, j = 1, left = [1, 2, 2], right = [3, 3, 4], median = 2.5

当 A = [1, 2, 3, 4], B = [2 ,3, 4] i = 2 , j = 1 left = [1, 2, 2], right = [3, 3, 4, 4], median = min(A[i], B[j]) = 3

这里的 j = (m + n) / 2 - i， 当为偶数时， 平均分配；当为奇数是，右边比左边多一个，且右边最小值为中位数。

这时来考虑一下边界条件：

当 i=0,i=m,j=0,j=n 值 A[i-1],B[j-1],A[i],B[j] 不存在，那怎么防止程序崩溃。

目的是找打值满足 max(left_part) <= min(left_right)。

如果 i, j 都不是边界值(意味着 A[i-1],B[j-1],A[i],B[j] 都存在有效)，那么需要确认 B[j-1] <= A[i] && A[i-1] <= B[j]。如果 A[i-1],B[j-1],A[i],B[j] 不存在，那么就没必要去确认上述两个条件；比如，i = 0, A[i - 1] 不存在，因此没必要去确认 A[ i - 1] <= B[j]. 因此， 只需要确认：

 (j == 0 or i == m or B[j-1] <= A[i]) and (i == 0 or j == n or A[i-1] <= B[j])

因此在二分查找的循环中，只需要判断以下条件：

<a> (j == 0 or i == m or B[j-1] <= A[i]) and
    (i == 0 or j = n or A[i-1] <= B[j])
    找到需要的 i 值

<b> j > 0 and i < m and B[j - 1] > A[i]
    i 太小，需要增加，但不能超过 m
    
<c> i > 0 and j < n and A[i - 1] > B[j]
    i 太大，需要较少，但要大于 0， 等于0 则进行 a 条件判断

上述条件中， 因为 i < m, j = (m+n+1)/2 - i > (m+n+1)/2 - m >= (2*m+1)/2 - m >= 0， 因此可以不用判断 j > 0; c 条件同上；

上述三个条件互斥， 因此先判断后续两个条件即可。

Accepted

Runtime: 240 ms, faster than 100.00% of Kotlin online submissions for Median of Two Sorted Arrays.

Memory Usage: 44.1 MB, less than 66.67% of Kotlin online submissions for Median of Two Sorted Arrays.

import org.testng.annotations.Test

fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
    val m = nums1.size
    val n = nums2.size
    if (m > n) {
        return findMedianSortedArrays(nums2, nums1)
    }
    var low = 0
    var high = m
    while (low <= high) {
        // 针对 nums1 进行 二分查找
        val i = low + (high - low).shr(1)
        val j = (m + n).shr(1) - i

        if (i < m && nums2[j - 1] > nums1[i]) {
            low = i + 1
        } else if (i > 0 && nums1[i - 1] > nums2[j]) {
            high = i - 1
        } else {
            // 找到想要的 i 值
            println(i)
            var minRight = 0
            minRight = when {
                i == m -> nums2[j]
                j == n -> nums1[i]
                else -> Math.min(nums1[i], nums2[j])
            }
            if ((m + n) % 2 == 1) {
                return minRight * 1.0
            }
            var maxLeft = 0
            maxLeft = when {
                i == 0 -> nums2[j - 1]
                j == 0 -> nums1[i - 1]
                else -> Math.max(nums1[i - 1], nums2[j - 1])
            }
            return 0.5 * (maxLeft + minRight)


//            var maxLeft = 0
//            maxLeft = when {
//                i == 0 -> nums2[j - 1]
//                j == 0 -> nums1[i - 1]
//                else -> Math.max(nums1[i - 1], nums2[j - 1])
//            }
//            if ((m + n) % 2 == 1) {
//                return maxLeft * 1.0
//            }
//            // 偶数逻辑
//            var minRight = 0
//            minRight = when {
//                i == m -> nums2[j]
//                j == n -> nums1[i]
//                else -> Math.min(nums1[i], nums2[j])
//            }
//            return 0.5 * (maxLeft + minRight)
        }
    }
    return 0.0
}

fun findMedianSortArray(nums1: ArrayList<Int>): Double {
    val m = nums1.size
    if (m == 0) {
        return 0.0
    }
    val low = 0
    val high = m
    val mid = low + (high - low).shr(1)
    if (m % 2 == 0) {
        return 0.5 * (nums1[mid] + nums1[mid - 1])
    } else {
        return nums1[mid] * 1.0
    }
}

@Test
fun _0004() {
    // 10    2 4 6 8 9
    val nums1 = IntArray(5)
    nums1[0] = 1
    nums1[1] = 2
    nums1[2] = 3
    nums1[3] = 4
    nums1[4] = 5
    val nums2 = IntArray(1)
    nums2[0] = 3
    val result = findMedianSortedArrays(nums1, nums2)
//    val result = findMedianSortArray(arrayListOf(1, 2))
    print(result)
}