1
2
3
4

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

则中位数是 2.0

1
2
3
4

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

则中位数是 (2 + 3)/2 = 2.5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    '''
    ## 解题思路
    -
    '''
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        a, b = sorted((nums1, nums2), key=len)
        m, n = len(a), len(b)
        l, h = 0, m
        mid = int((m + n - 1) / 2)  # mid for total nums1 and nums2
        while l < h:
            i = int((l + h) / 2)  # mid of nums1
            if i > mid - 1 or a[i] >= b[mid - 1 - i]:  # nums1 当前
                h = i  #
            else:
                l = i + 1  #
        i = l
        nextfew = sorted(a[i:i+2] + b [mid-i: mid-i+2])
        return (nextfew[0] + nextfew[1-(m+n)%2]) / 2.0

 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

impl Solution {
    /// ## 解题思路
    /// - 划分法 + 二分查找法
    /// 1. 对于nums1, nums2, 其排序后的中位数按合并后数组(设为nums)总长度(m+n)可以分为两种：
    ///     a. 总长度为偶数, 中位数为中间两个数和/2;
    ///     b. 总长度为奇数，中位数为中间数(nums[(m+n)/2])；
    /// 2. 由于nums1，nums2都为有序数组，合并后nums1,nums2各元素的先后次序不变；
    /// 3. 合并后数组中位数处将nums1,nums2分别切为前后两个部分，设切开元素的索引分别为i，j：
    ///     nums1[0], nums1[1], ..., nums1[i-1], | nums1[i], ..., nums1[m]
    ///     nums2[0], nums2[1], ..., nums2[j-1], | nums2[j], ..., nums2[n]
    ///     显然, 必须满足：
    ///         nums1[i-1] <= nums2[j]    ......... (1)
    ///         nums2[j-1] <= nums1[i]  ......... (2)
    ///     可以证明，(1)可推导出(2)
    /// 4. 如果总数组长度为偶数，则：
    ///     len(nums1[0..i-1]) + len(nums2[0..j_1]) = len(nums1[i..]) + len(nums2[j..]),
    ///    即：
    ///      i+j = len(nums1) -i + len(nums2) -j
    ///    => i + j = (len(nums1) + len(nums2) ) / 2
    ///      此时中位数为:
    ///             (max(nums1[i-1], nums2[j-1]) + min(nums1[i], nums2[j]) ) / 2
    ///    如果总长度为奇数，则：
    ///     len(nums1[0..i-1]) + len(nums2[0..j-1]) = len(nums1[i..]) + len(nums2[j..]) + 1
    ///    即：
    ///     i+j = len(nums1) -i + len(nums2) -j  + 1
    ///    =>  i + j = (len(nums1) + len(nums2) + 1) / 2
    ///    此时中位数为:
    ///             max(nums[i-1], nums[j-1])
    ///    将上述两种情况综合一下，i,j 满足如下：
    ///       i + j = (len(nums1) + len(nums2) + 1) / 2
    ///    =>
    ///        j =  (len(nums1) + len(nums2) + 1) / 2 - i
    /// 5. 因此，只需要找到满足条件的i, 使nums1[i-1] <= nums2[j]即可；
    /// 6. 由于nums1，nums2都是有序的，可以使用二分查找来确定i;
    pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
        // 将nums1，nums2中数组长度短的置前
        let (nums1, nums2) = if nums1.len() < nums2.len() {
            (nums1, nums2)
        } else {
            (nums2, nums1)
        };

        let (m, n) = (nums1.len(), nums2.len());
        let (mut l, mut r) = (0, m);
        let (mut mid1, mut mid2) = (0, 0);
        // 寻找i
        while l <= r {
            let i = (l + r) / 2;
            let j = (m + n + 1) / 2 - i;

            let num1_i_1 = if i == 0 { std::i32::MIN } else { nums1[i-1] };
            let num2_j_1 = if j == 0 { std::i32::MIN } else { nums2[j-1] };
            let num1_i = if i == m { std::i32::MAX } else { nums1[i] };
            let num2_j = if j == n { std::i32::MAX } else { nums2[j] };

            if num1_i_1 <= num2_j {
                mid1 = std::cmp::max(num1_i_1, num2_j_1);
                mid2 = std::cmp::min(num1_i, num2_j);
                l = i + 1;
            } else {
                r = i - 1;
            }
        }

        if (m+n) % 2 == 0 {
            (mid1+mid2) as f64 / 2.0_f64
        } else {
            mid1 as f64
        }
    }
}