1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
TreeSet<Integer> visited = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
Integer ceiling = visited.ceiling(nums[i]);
if (ceiling != null && ceiling - nums[i] <= valueDiff)
return true;
Integer floor = visited.floor(nums[i]);
if (floor != null && nums[i] - floor <= valueDiff)
return true;
visited.add(nums[i]);
if (visited.size() > indexDiff) {
visited.remove(nums[i - indexDiff]);
}
}
return false;
}
}
|
维护一个sliding window. 这个我是想到了, 但是我没想到如何找出这个sliding window里面的比nums[i]小的数字中最大的和比它大的数字中最小的, 想到了binary search也没想到用BST.
你可能会问, 14行把nums[i - indexDiff]给移走了, 那如果区间内有多个这个元素, 那岂不是都移走了? 答案是不会有多个这个元素, 因为如果有的话, 我们在之前的遍历中某个时刻就会在ceiling或者floor的时候就会捕捉到这个nums[i - indexDiff], 因为此时当前元素和它相差为0. 但是并没有捕捉到说明这个元素只出现过一次. 这也是为什么这道题能用TreeSet的原因, TreeSet是红黑树但是每个元素的值都不相同.
时间复杂度: O(nlog(min(n, k)))
空间复杂度: O(min(n, k))
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
| class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
if (valueDiff < 0)
return false;
Map<Integer, Integer> numBucket = new HashMap<>();
int width = valueDiff + 1;
for (int i = 0; i < nums.length; i++) {
int id = getID(nums[i], width);
if (numBucket.containsKey(id))
return true;
if (numBucket.containsKey(id - 1) && nums[i] - numBucket.get(id - 1) <= valueDiff)
return true;
if (numBucket.containsKey(id + 1) && numBucket.get(id + 1) - nums[i] <= valueDiff)
return true;
numBucket.put(id, nums[i]);
if (i >= indexDiff) {
numBucket.remove(getID(nums[i - indexDiff], width));
}
}
return false;
}
private int getID(int num, int width) {
return num < 0 ? (num + 1) / width - 1 : num / width;
}
}
|
这个思路就是看到有slidng window或者说是一个范围, 我们可以试着用bucket. 我们假设一个bucket的范围是valueDiff, 也就是[0, valueDiff]范围可以形成一个bucket, [valueDiff + 1, 2 * valueDiff + 1]可以形成一个bucket. 我们看每个num都在哪个bucket里面. 如果两个num在同一个bucket中, 那他俩的距离一定小于valueDiff, 另一种可能是两个num在相邻的bucket中, 此时我们就要手动检查二者的距离了. 需要注意的是, 我们只能维护indexDiff个buckets, 如果超出了, 我们就要把最靠前的数字所在的bucket给删掉.
你可能会问, 这样删除的话, 会不会把在window中但是值相同的数字删掉. 答案是不会的, 如果有重复的数字, 我们之前的逻辑就会捕捉捉到也就是一上来看某个nums[i]所在的bucket是否存在. 这也保证每个bucket只有一个数字. 这是关键.
每个bucket只有一个数字.
时间复杂度: O(n)
空间复杂度: O(min(n, k))
