每日小刷
Runtime | Memory |
---|---|
0ms | 2.6m |
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工程師