LeetCode 220 辛苦老师了
来源:4-8 二分搜索树底层实现的顺序性 Contain Duplicate III
慕妹2978617
2020-04-15
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums.length == 0)
return false;
TreeSet<Long> set = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
long num = nums[i];
//num-t<= x <=num+t 查看是否存在这个x 找到大于 num-t的最小值 同时 这个值在[num-t,num+t]这个范围内就是成功的
Long ceiling = set.ceiling((long)num - t);
if (ceiling != null && ceiling <=(long) num + t)
return true;
set.add(num);
if (set.size() == k + 1) {
set.remove((long)nums[i - k]);
}
}
return false;
}
这里有2个问题:
- 对于k 我们用Set存 如果遇到重复元素 那么Set.size()>=k ,按照思想这个是一定的。但是看leetcode说根据我们的判断遇到重复元素会直接true,这是为什么,我们找到合适的例子,辛苦老师帮我解释下,最好能有个例子,我动笔试试
- 这个例子中是不可能出现负数的,但是老师在别的问答区说t可以为负数,那么对于这个例子[1,0,1,-1]
k=1
t=-2
-t=<|i-j|=<t [-2,2]
1-(-1)=2 其实是满足 但是会返回false 为什么?
辛苦老师!本身小白,感觉我太能问问题了,不过其实我已经看了很多解法的解释,和文章,感觉总是顺着正确的思路去走,反而会出现新的问题 辛苦老师了 ,最好能举个例子
写回答
1回答
-
1
其实我没有特别理解的你的问题。
我们在每轮循环中,其实是在看连续的 k 个元素中,是否有一个元素,和 num 的距离在 t 以内。如果存在一个元素,和 num 相同的话,那么 set.ceiling((long)num - t) 的结果,至少为 num 本身。那么下面的判断中,ceiling <=(long) num + t 一定是真的,就返回 true 了。
找一组存在相同元素的数据试试看?
2
“这个例子中是不可能出现负数的,但是老师在别的问答区说t可以为负数。"
具体你说的是哪个值不能出现负数?这个问题中,t 不可能是负数,否则没意义。但是 num - t 可能为负数。
更正:我测了一下,问题的测试用例中,t 可能是负数。此时直接返回 false 就好了。因为 nums [i] 和 nums [j] 的差的绝对值最大为 t。而 nums [i] 和 nums [j] 的差的绝对值肯定 >= 0。所以如果 t 是负数,肯定不存在,直接返回 false 就好。
继续加油!:)
032020-04-16
相似问题