[−][src]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 }