LeetCode 219 & 220

来源：4-8 二分搜索树底层实现的顺序性 Contain Duplicate III

慕妹2978617

2020-04-15

上个问题我可能没表达清楚219 list替换Set

这里重新提问同时219和220 两道题

LeetCode 219

图片描述这个问题课程代码：

 public static boolean containsNearbyDuplicate2(int[] nums, int k) {


        //遍历nums中范围的值 这里用list 删除元素会错乱
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (set.contains(num)) {
                return true;
            }
            set.add(num);
            if (set.size() == k + 1) {
                set.remove(nums[i - k]);
            }
        }

老师我用list这个解法就是错的，我debug打印几次list发现 list.remove 当是Integer时集合List他不知道时删除元素还是删除索引，所以会错乱，但是我这里还是有点怀疑，list顺序添加可以顺序取出的吧？这个问题不能用list的原因是因为 remove这个方法的原因吗？

LeetCode 220

图片描述
课程解法：

  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;
    }

这里有1个问题：

对于k 我们用Set存如果遇到重复元素那么Set.size()>=k ，按照思想这个是一定的。但是看leetcode说根据我们的判断遇到重复元素会直接true，这是为什么，我们找到合适的例子，辛苦老师帮我解释下，最好能有个例子，我动笔试试

辛苦老师！

写回答

2回答

liuyubobobo

2020-04-15

已采纳

在之前的问题里已经回复你里：set.remove(x) 的意思是从 set 中删除掉 x 这个元素；但是 list.remove(x) 的意思是删除掉 x 索引所在的元素。二者的参数意思是不一样的。

所以，如果 set 是一个 list 的话，set.remove(nums[i - k]); 的意思，不是从这个 list 里删除 nums[i - k] 这个元素，而是把 nums[i - k] 看做一个索引，删除掉在 nums[i - k] 这个索引位置的元素。

比如对 [4, 3, 2, 1, 0] 这个数组，如果你想删除掉 4，应该调用 list.remove(0)，而不是 list.remove(4)。如果调用 list.remove(4)，最后删掉的是 0。因为 0 在索引 4 的位置；4 在索引 0 的位置。

对于这个问题，其实你每次删除第一个元素就好了。使用 LinkedList 或者 ArrayList，只需要这么写，就是正确的：

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        //遍历nums中范围的值 这里用list 删除元素会错乱
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (list.contains(num)) {
                return true;
            }
            list.add(num);
            if (list.size() == k + 1) {
                list.remove(0); // 删除掉最早的元素
            }
        }
        return false;
    }
}

但是，这么做会超时，这是因为 list.contains(num) 此时是 O(n) 的，整个算法的时间复杂度是 O(n^2) 的。

继续加油！：）

慕妹2978617

非常感谢！

2020-04-16

共1条回复