220. Contains Duplicates

stonezhu 发布于2019-08-14 14:24 / 3018人阅读

摘要：题目解答这一题有两个思路，都是参考里写出来的。是更加直接的用和来看有没有在这个范围内存在的数。

题目：
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 < 1 || t < 0) return false;
    Map map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        long remappedNum = (long) nums[i] - Integer.MIN_VALUE;
        long bucket = remappedNum / ((long) t + 1);
        if (map.containsKey(bucket) || (map.containsKey(bucket - 1) && remappedNum - map.get(bucket - 1) <= t) || (map.containsKey(bucket + 1) && map.get(bucket + 1) - remappedNum <= t)) {
            return true;
        }
        if (map.entrySet().size() >= 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 < 1 || t < 0) return false;
    TreeSet values = new TreeSet(); 
    for (int i = 0; i < nums.length; i++) {
        Integer floor = values.floor(nums[i] + t);
        Integer ceiling = values.ceiling(nums[i] - t);
        if ((floor != null && floor >= nums[i]) || (ceiling != null && ceiling <= nums[i])) {
            return true;
        }
        if (values.size() >= k) {
            values.remove(nums[i - k]);
        }
        values.add(nums[i]);
    }
    return false;
}

服务器托管云服务器 Duplicates Contains 220cdn 企业邮箱220

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64989.html

leetcode217.219.220 contains duplicate

摘要：输入一个整数数组，查看数组中是否存在重复的值。新的数组中数组的下标为原数组的值，如果遍历过，则设置为。这里使用了作为实现的数据结构，通过堆的形式对集合中的数据进行存储，从而我们可以通过某种顺序获得该集合中的所有顺序。 217 Contains Duplicate Given an array of integers, find if the array contains any dup...

tulayang 2019-08-16 10:56 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
220. Contains Duplicate III

摘要：如果不是，则在相邻的两个内再找。如果相邻的内元素绝对值只差在以内，说明我们知道到了，返回为了保证，我们在时，删除对应的的元素都会落在里。为了解决这个问题，所有元素横移。 Given an array of integers, find out whether there are two distinct indices i and j in the array such that th...

王伟廷 2019-08-16 10:36 评论0 收藏0
[LeetCode] Contains Duplicate

Contains Duplicate Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false ...

褰辩话 2019-08-19 10:43 评论0 收藏0
[Leetcode] Contains Duplicate 包含重复

摘要：代码集合法复杂度时间空间思路同样使用集合，但这次我们要维护集合的大小不超过，相当于是记录一个宽度为的窗口中出现过的数字。 Contains Duplicate I Given an array of integers, find if the array contains any duplicates. Your function should return true if any v...

rozbo 2019-08-14 12:28 评论0 收藏0