220. Contains Duplicates

题目：
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.

解答：
这一题有两个思路，都是参考discussion里写出来的。一个是bucket, 一个是TreeSet。
1.bucket是按照两个数最多相差t这个性质，把每个数分到不一样的bucket里，在k范围内，如果有两个数在同一个bucket里，那么说明这两个数满足条件；或者相邻的bucket里存在一个数，而且与这个数的差小于等于t，那这个数也满足；其它都是超出范围的。

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (k map = new HashMap();
for (int i = 0; i = k) {
long lastBucket = ((long) nums[i - k] - Integer.MIN_VALUE) / ((long) t + 1);
map.remove(lastBucket);
}
map.put(bucket, remappedNum);
}
return false;
}
2.TreeSet是更加直接的用floor和ceiling来看有没有在这个范围内存在的数。

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (k values = new TreeSet();
for (int i = 0; i = nums[i]) || (ceiling != null && ceiling = k) {
values.remove(nums[i - k]);
}
values.add(nums[i]);
}
return false;
}

关键字：java, bucket, leetcode, nums

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！