每日小刷

median-of-two-sorted-arrays/

use std::cmp;
impl Solution {
    // 2i + 2j = m+n
    // i = (m+n)/2 - j;
    // (m+n)/2>i
    // n>m 保證j > 0
    pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
        let mut iMin = 0;
        let mut iMax = 0;
        let mut m: Vec<i32>;
        let mut n: Vec<i32>;

        if nums1.len() > nums2.len() {
            m = nums2;
            n = nums1;
        } else {
            m = nums1;
            n = nums2;
        }
        iMax = m.len();
        // 二分查找符合條件的變量
        while iMin <= iMax {
            println!("iMin:{:?},iMax:{:?}", iMin, iMax);
            let i = (iMin + iMax) / 2;
            let j = (m.len() + n.len() + 1) / 2 - i;
            if i > iMin && n[j] < m[i - 1] {
                iMax = i - 1;
            } else if i < iMax && m[i] < n[j - 1] {
                iMin = i + 1;
            } else {
                // perfect
                let mut left_max = 0;
                // get left_max
                if i == 0 {
                    left_max = n[j - 1];
                } else if j == 0 {
                    left_max = m[i - 1];
                } else {
                    left_max = cmp::max(n[j - 1], m[i - 1]);
                }

                if (m.len() + n.len()) % 2 == 1 {
                    return left_max as f64;
                }
                let mut right_min = 0;

                if i == m.len() {
                    right_min = n[j];
                } else if j == n.len() {
                    right_min = m[i];
                } else {
                    right_min = cmp::min(n[j], m[i]);
                }
                return (left_max as f64 + right_min as f64) / 2.0;
            }
        }
        0.0
    }
}

好好學(xué)習(xí)rust和基礎(chǔ)算法

目標(biāo)：rust工程師