Function leetcode_for_rust::cd0004_median_of_two_sorted_arrays::find_median_sorted_arrays

pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64

Solutions

Approach 1: Recursive Approach

• Time complexity: O(log(min(m,n)))

• Space complexity: O(1)

• Runtime: 0 ms

• Memory: 2.5 MB

// 思路
// 将 nums1 与 nums2 使用二分法分别将其拆分为两半, nums1_left, nums1_right, nums2_left, nums2_right；
// 将 nums1_left 与 nums2_left 合并 part_left；nums1_right 与 nums2_right 合并 part_right
// 当 part_left == part_right 且 max(part_left)≤min(part_right) 时，中间数即为 (max(left_part)+min(right_part)) / 2
pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
    let mut first = &nums1;
    let mut second = &nums2;

    if first.len() > second.len() {
        first = &nums2;
        second = &nums1
    }

    let m = first.len();
    let n = second.len();
    let mut low = 0;
    let mut high = m;
    let half_len = ((n - m + 1) >> 1) + m;

    while low <= high {
       let mid_first = ((high - low) >> 1) + low;
       let mid_second = half_len - mid_first;

       let first_left = if mid_first == 0 { std::i32::MIN } else { first[mid_first - 1] };
       let first_right = if mid_first == m { std::i32::MAX } else { first[mid_first] };
       let second_left = if mid_second == 0 { std::i32::MIN } else { second[mid_second - 1] };
       let second_right = if mid_second == n { std::i32::MAX } else { second[mid_second] };

       if first_left <= second_right && second_left <= first_right {
           if (n + m) & 1 == 0 {
               // 避免溢出，不使用 (right_min + left_max) as f64 / 2.0 的方式
               let mut left_max = first_left.max(second_left);
               let mut right_min = first_right.min(second_right);
               if left_max > right_min {
                   let tmp = left_max;
                   left_max = right_min;
                   right_min = tmp;
               }
               return (right_min - left_max) as f64 / 2.0 + (left_max as f64);
           } else {
               return first_left.max(second_left) as f64
           }
       } else if first_left > second_right {
           high = mid_first - 1;
       } else {
           low = mid_first + 1;
       }
    }
    0.0
}