-
Notifications
You must be signed in to change notification settings - Fork 34
/
Solution.java
46 lines (44 loc) · 1.23 KB
/
Solution.java
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
42
43
44
45
46
class MedianFinder {
List<Integer> list=new ArrayList<Integer>();
// Adds a number into the data structure.
public void addNum(int num) {
if(list.size()==0){
list.add(num);
}else{
int s=0;
int e=list.size()-1;
int m=(s+e)/2;
while(e-s>1){
if(list.get(m)==num){
list.add(m,num);
return;
}
if(list.get(m)<num){
s=m;
}else{
e=m;
}
m=(s+e)/2;
}
if(list.get(e)<num){
list.add(e+1,num);
}else if(list.get(s)>num){
list.add(s,num);
}else{
list.add(e,num);
}
}
}
// Returns the median of current data stream
public double findMedian() {
if(list.size()==0){
return (double)0;
}
int length=list.size();
return ((double)list.get(length/2)+(double)list.get((length-1)/2))/2.0;
}
};
// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();
// mf.addNum(1);
// mf.findMedian();