220. Contains Duplicate III
Question
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
Solution
保证indexd的差在一定范围内,用sliding window. 保证window中两个元素的差<=t,考虑以下两种方法:
方法一:利用TreeSet的数据结构,使用.floor(n)方法返回小于n的元素中的最大者,如果不存在则返回null,使用.ceiling(n)方法返回大于n的元素中的最小者,如果不存在则返回null。然后看当前元素nums[i]和这两个元素的差是否小于t,只要有一个小于就返回true。这里要注意的是,两个int的数相加或者相减很可能overflow,因此要将其转化为long再做比较。
方法二:利用bucket sort的思想,将每个num放到不同的bucket中去,然后只要比较当前的bucket以及前后的bucket就可以了,具体推导方法如下:
如果: | nums[i] - nums[j] | <= t 式a
等价: | nums[i] / t - nums[j] / t | <= 1 式b
推出: | floor(nums[i] / t) - floor(nums[j] / t) | <= 1 式c
等价: floor(nums[j] / t) ∈ {floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1} 式d
那么对于每一个num,只要key = num / t,然后搜寻(key-1, key, key + 1)是否在维护的最大size为k的map中,并且判断真实的value diff是否<= t就可以了。
在这里要注意两点:
1)我们将通式key = num/t变为key = num / Math.max(1,t)是为了应对当t为0时的情况,虽然这时的key会和t=1时相同,但是在后面判断真实的value diff是否<= t时依然可以根据t的真实值进行判断。
2)因为要搜寻key-1,key+1,因此当key为边界情况时可能造成overflow,因此要将map中的key转换成long进行存储,同时因为涉及到要判断真实的value diff是否<= t,这时也有可能出现overflow的情况,因此value也要转换成long进行存储。
代码如下:
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums == null || nums.length <= 1) {
return false;
}
if (k < 1 || t < 0) {
return false;
}
//TreeSet version
// long diff = t;
// TreeSet<Integer> set = new TreeSet<>();
// for (int i = 0; i < nums.length; i++) {
// int curt = nums[i];
// if ((set.floor(curt) != null && curt <= diff + set.floor(curt)) || (set.ceiling(curt) != null && set.ceiling(curt) <= diff + curt)) {
// return true;
// }
// set.add(curt);
// if (i >= k) {
// set.remove(nums[i - k]);
// }
// }
//Bucket version
HashMap<Long, Long> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (i > k) {
int removeElement = nums[i - k - 1];
long key = getId(removeElement, t);
map.remove(key);
}
int curt = nums[i];
long curtKey = getId(curt, t);
if (map.containsKey(curtKey) && Math.abs(map.get(curtKey) - nums[i]) <= t) {
return true;
}
if (map.containsKey(curtKey - 1) && Math.abs(map.get(curtKey - 1) - nums[i]) <= t) {
return true;
}
if (map.containsKey(curtKey + 1) && Math.abs(map.get(curtKey + 1) - nums[i]) <= t) {
return true;
}
map.put(curtKey, (long)curt);
}
return false;
}
private long getId(int n, int t) {
return (long)n / Math.max(1, t);
}
}