/
895.java
79 lines (73 loc) · 2.31 KB
/
895.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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
__________________________________________________________________________________________________
sample 75 ms submission
class FreqStack {
private Map<Integer, Integer> map;
private List<LinkedList<Integer>> list;
private int index;
private int counter;
public FreqStack() {
this.map = new HashMap<>();
this.list = new ArrayList<>();
this.counter = 0;
this.index = -1;
}
public void push(int x) {
int count = map.getOrDefault(x, 0);
if(count == list.size())
{
LinkedList<Integer> stack = new LinkedList<>();
stack.addLast(x);
list.add(stack);
}
else
{
LinkedList stack = list.get(count);
stack.addLast(x);
}
index = index < count ? count : index;
map.put(x, count+1);
}
public int pop() {
LinkedList<Integer> indexList = list.get(index);
int ans = indexList.pollLast();
map.put(ans, index);
if(indexList.size()==0)
{
index--;
}
return ans;
}
}
/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack obj = new FreqStack();
* obj.push(x);
* int param_2 = obj.pop();
*/
__________________________________________________________________________________________________
sample 54608 kb submission
class FreqStack {
HashMap<Integer, Integer> freq = new HashMap<>();
HashMap<Integer, Stack<Integer>> m = new HashMap<>();
int maxfreq = 0;
public void push(int x) {
int f = freq.getOrDefault(x, 0) + 1;
freq.put(x, f);
maxfreq = Math.max(maxfreq, f);
if (!m.containsKey(f)) m.put(f, new Stack<Integer>());
m.get(f).add(x);
}
public int pop() {
int x = m.get(maxfreq).pop();
freq.put(x, maxfreq - 1);
if (m.get(maxfreq).size() == 0) maxfreq--;
return x;
}
}
/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack obj = new FreqStack();
* obj.push(x);
* int param_2 = obj.pop();
*/
__________________________________________________________________________________________________