diff options
Diffstat (limited to 'other/find_median_data_stream.rs')
-rw-r--r-- | other/find_median_data_stream.rs | 41 |
1 files changed, 41 insertions, 0 deletions
diff --git a/other/find_median_data_stream.rs b/other/find_median_data_stream.rs new file mode 100644 index 0000000..1ef5252 --- /dev/null +++ b/other/find_median_data_stream.rs @@ -0,0 +1,41 @@ +use std::cmp::Reverse; +use std::collections::BinaryHeap; +#[derive(Default)] +struct MedianFinder { + small: BinaryHeap<i32>, + large: BinaryHeap<Reverse<i32>>, + odd: bool +} + +impl MedianFinder { + fn new() -> Self { + Default::default() + } + fn add_num(&mut self, num: i32) { + if self.odd { + self.small.push(num); + if let Some(max) = self.small.pop() { + self.large.push(Reverse(max)); + } + } else { + self.large.push(Reverse(num)); + if let Some(Reverse(min)) = self.large.pop() { + self.small.push(min);; + } + } + self.odd = !self.odd; + } + fn find_median(&self) -> f64 { + if self.odd { + *self.small.peek().unwrap() as f64 + } else { + (self.small.peek().unwrap() + self.large.peek().unwrap().0) as f64 / 2.0 + } + } +} + +fn main() { + let obj = MedianFinder::new(); + obj.add_num(num); + let ret_2: f64 = obj.find_median(); +} |