diff options
Diffstat (limited to 'src/bin')
| -rw-r--r-- | src/bin/p0004.rs | 96 |
1 files changed, 96 insertions, 0 deletions
diff --git a/src/bin/p0004.rs b/src/bin/p0004.rs new file mode 100644 index 0000000..2925500 --- /dev/null +++ b/src/bin/p0004.rs @@ -0,0 +1,96 @@ +use std::cmp::{min, max}; + +impl Solution { + fn vec_get(v: &Vec<i32>, n: i32) -> i32 { + if n < 0 { + return i32::MIN; + } + if n >= v.len() as i32 { + return i32::MAX; + } + return v[n as usize]; + } + pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 { + let mut n1 = &nums1; + let mut n2 = &nums2; + if n1.len() < n2.len() { + n1 = &nums2; + n2 = &nums1; + } + + if n2.len() == 0 || n1[n1.len()-1] <= n2[0] { + if (n1.len() + n2.len()) % 2 == 0 { + let mid_index = (n1.len() + n2.len()) / 2; + let right: i32; + if mid_index == n1.len() { + right = n2[0]; + } else { + right = n1[mid_index]; + } + return (n1[mid_index - 1] + right) as f64 / 2.0; + } else { + let mid_index = (n1.len() + n2.len()) / 2; + return n1[mid_index] as f64; + } + } + if n2[n2.len()-1] <= n1[0] { + if (n1.len() + n2.len()) % 2 == 0 { + let mid_index = (n1.len() + n2.len()) / 2 - n2.len(); + let left: i32; + if mid_index <= 0 { + left = n2[n2.len() - 1]; + } else { + left = n1[mid_index - 1]; + } + return (left + n1[mid_index]) as f64 / 2.0; + } else { + let mid_index = (n1.len() + n2.len()) / 2 - n2.len(); + return n1[mid_index] as f64; + } + } + + let mut left: i32 = 0; + let mut right: i32 = n1.len() as i32 - 1; + let mut mid: i32 = 0; + let mut mid2: i32 = 0; + loop { + if left > right { break; } + println!("left: {}, right: {}", left, right); + mid = (left + right) / 2; + mid2 = (n1.len() + n2.len()) as i32 / 2 - (1 + mid) - 1; + if mid2 < -1 { + right = mid - 1; + continue; + } + if mid2 >= n2.len() as i32 { + left = mid + 1; + continue; + } + if n1[mid as usize] > Self::vec_get(n2, mid2 + 1) { + right = mid - 1; + continue; + } + if n1[mid as usize + 1] < Self::vec_get(n2, mid2) { + left = mid + 1; + continue; + } + break; + } + if (n1.len() + n2.len()) % 2 == 0 { + (max(n1[mid as usize], Self::vec_get(n2, mid2)) + + min(n1[mid as usize + 1], Self::vec_get(n2, mid2 + 1))) as f64 / 2.0 + } else { + min(n1[mid as usize +1], Self::vec_get(n2, mid2 + 1)) as f64 + } + } +} + +struct Solution {} +fn main() { + println!("{}", Solution::find_median_sorted_arrays(vec![1,2,3], vec![4,5,6])); + println!("{}", Solution::find_median_sorted_arrays(vec![4,5,6], vec![1,2,3])); + println!("{}", Solution::find_median_sorted_arrays(vec![1,2,3], vec![5,6])); + println!("{}", Solution::find_median_sorted_arrays(vec![4,5,6], vec![1,2])); + println!("{}", Solution::find_median_sorted_arrays(vec![1,3,5], vec![2,4,6])); + println!("{}", Solution::find_median_sorted_arrays(vec![3], vec![1,2,4,5])); +}
\ No newline at end of file |