/
KthLargestElementInStream.java
66 lines (55 loc) · 1.69 KB
/
KthLargestElementInStream.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
// https://leetcode.com/problems/kth-largest-element-in-a-stream/
class KthLargest {
TreeSet<Integer> set;
Map<Integer, Integer> freq;
int k = 0, count = 0;
public KthLargest(int k, int[] nums) {
set = new TreeSet<>();
freq = new HashMap<>();
this.k = k;
Arrays.sort(nums);
if (nums.length != 0 && k <= nums.length) {
for (int i = nums.length - k; i < nums.length; i++) {
set.add(nums[i]);
freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);
count++;
}
} else {
for (int i = 0; i < nums.length; i++) {
set.add(nums[i]);
freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);
count++;
}
}
}
public int add(int val) {
if (set.isEmpty()) {
set.add(val);
freq.put(val, 1);
count++;
return val;
}
if (k > count) {
set.add(val);
freq.put(val, freq.getOrDefault(val, 0) + 1);
count++;
return set.first();
}
int f = set.first();
if (val > f) {
int firstFreq = freq.get(f);
if (firstFreq == 1) {
set.remove(f);
} else {
freq.put(f, firstFreq - 1);
}
set.add(val);
freq.put(val, freq.getOrDefault(val, 0) + 1);
/*if (set.first() != val) {
set.add(f);
}*/
}
//System.out.println(set);
return set.first();
}
}