-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_220.java
More file actions
63 lines (58 loc) · 1.97 KB
/
Copy pathP_220.java
File metadata and controls
63 lines (58 loc) · 1.97 KB
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
package leetcode.medium;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
public class P_220 {
public boolean containsNearbyAlmostDuplicateTS(int[] nums, int k, int t) {
if (t < 0) { return false; }
final TreeSet<Integer> ts = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
if (!ts.add(nums[i])) {
return true;
}
final Integer higher = ts.higher(nums[i]);
final Integer lower = ts.lower(nums[i]);
if (higher != null && higher <= t + nums[i]) {
return true;
}
if (lower != null && nums[i] <= t + lower) {
return true;
}
if (ts.size() > k) {
ts.remove(nums[i - k]);
}
}
return false;
}
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (t <= 0) { return t == 0 ? containsNearbyDuplicate(nums, k) : false; }
final Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
final int m = Math.floorDiv(nums[i], t);
if (map.containsKey(m)
|| (map.containsKey(m - 1) && Math.abs(nums[i] - map.get(m - 1)) <= t)
|| (map.containsKey(m + 1) && Math.abs(nums[i] - map.get(m + 1)) <= t)) {
return true;
}
map.put(m, nums[i]);
if (i >= k) {
map.remove(Math.floorDiv(nums[i - k], t));
}
}
return false;
}
public boolean containsNearbyDuplicate(int[] nums, int k) {
final Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (!set.add(nums[i])) {
return true;
}
if (set.size() > k) {
set.remove(nums[i - k]);
}
}
return false;
}
}