blob: 1ef5252c086eddd48ae7d322d0c88e7d4ec01567 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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();
}
|