-
Notifications
You must be signed in to change notification settings - Fork 0
/
898.bitwise-ors-of-subarrays.java
62 lines (51 loc) · 1.61 KB
/
898.bitwise-ors-of-subarrays.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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class FreqStack {
HashMap<Integer, Integer> hsm;
int i;
TreeMap<Integer, TreeSet<Integer>> tsm;
HashMap<Integer, Integer> mapr;
public FreqStack() {
hsm = new HashMap<>();
mapr = new HashMap<>();
tsm = new TreeMap<>();
i = 0;
// maxfreq = 0;
}
public void push(int x) {
mapr.put(i, x);
if(!hsm.containsKey(x)){
hsm.put(x , 0);
if(!tsm.containsKey(1))
tsm.put(1, new TreeSet<Integer>());
tsm.get(1).add(i);
}
else{
// System.out.println("bef" +" "+tsm);
if(!tsm.containsKey(hsm.get(x)+1))
tsm.put(hsm.get(x)+1, new TreeSet<Integer>());
tsm.get(hsm.get(x)+1).add(i);
// System.out.println(tsm);
}
hsm.put(x, hsm.get(x)+1);
i++;
}
public int pop() {
int maxkey = -1;
int maxfreq = tsm.lastKey();
int maxkeyind = tsm.get(maxfreq).last();
tsm.get(maxfreq).remove(maxkeyind);
if(tsm.get(maxfreq).size() == 0)
tsm.remove(maxfreq);
// System.out.println(mapr.get(maxkeyind) +" "+hsm+" "+tsm);
if(hsm.get(mapr.get(maxkeyind)) == 1)
hsm.remove(mapr.get(maxkeyind));
else
hsm.put(mapr.get(maxkeyind), hsm.get(mapr.get(maxkeyind))-1);
return mapr.get(maxkeyind);
}
}
/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack obj = new FreqStack();
* obj.push(x);
* int param_2 = obj.pop();
*/