leetcode_rust/
find_median_sorted_arrays.rs

1#![allow(dead_code)]
2
3// todo
4// let nums1[0..i-1]'s length + nums2[0..j-1]'s length == the rest's length
5pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
6    let m = nums1.len();
7    let n = nums2.len();
8    let nums3;
9    let nums4;
10    if m > n {
11        nums3 = nums2;
12        nums4 = nums1;
13    } else {
14        nums3 = nums1;
15        nums4 = nums2;
16    }
17    let mut i_min = 0;
18    let mut i_max = m;
19    let half = (m + n + 1) / 2;
20    while i_min <= i_max {
21        let i = (i_min + i_max) / 2;
22        let j = half - i;
23        if i < i_max && nums4[j - 1] > nums3[i] {
24            i_min = i + 1;
25        } else if i > i_min && nums3[i - 1] > nums4[j] {
26            i_max = i - 1;
27        } else {
28            let max_left;
29            if i == 0 {
30                max_left = nums4[j - 1];
31            } else if j == 0 {
32                max_left = nums3[i - 1];
33            } else {
34                max_left = nums3[i - 1].max(nums4[j - 1]);
35            }
36            if (m + n) % 2 == 1 {
37                return max_left as f64;
38            }
39
40            let min_right;
41            if i == m {
42                min_right = nums4[j];
43            } else if j == n {
44                min_right = nums3[i];
45            } else {
46                min_right = nums3[i].max(nums4[j]);
47            }
48            return (max_left + min_right) as f64 / 2.0;
49        }
50    }
51    0f64
52}
53
54#[cfg(test)]
55mod tests {
56
57    #[test]
58    fn test1() {
59        //        assert_eq!(find_median_sorted_arrays(vec![1, 3], vec![2]), 2.0f64);
60        //        assert_eq!(find_median_sorted_arrays(vec![1,2], vec![3,4]), 2.5f64);
61        //        assert_eq!(find_median_sorted_arrays(vec![], vec![1]), 1f64);
62        //        assert_eq!(find_median_sorted_arrays(vec![1], vec![1]), 1f64);
63    }
64}
leetcode_rust/find_median_sorted_arrays.rs

leetcode_rust/
find_median_sorted_arrays.rs
