diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /other/find_median_data_stream.rs | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip |
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(); +} |