存在重复元素

2021-01-29

220. 存在重复元素 III

难度：中等

在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 ķ 。

如果存在则返回 true，不存在返回 false。

示例 1:

1 2	输入: nums = [1,2,3,1], k = 3, t = 0 输出: true

示例 2:

1 2	输入: nums = [1,0,1,1], k = 1, t = 2 输出: true

示例 3:

1 2	输入: nums = [1,5,9,1,5,9], k = 2, t = 3 输出: false

滑动窗口（超时）

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    for (int i = 0; i < nums.length; ++i) {
        for (int j = Math.max(i - k, 0); j < i; ++j) {
            if (Math.abs(nums[i] - nums[j]) <= t) return true;
        }
    }
    return false;
}
// Time limit exceeded.

作者：LeetCode
链接：https://leetcode-cn.com/problems/contains-duplicate-iii/solution/cun-zai-zhong-fu-yuan-su-iii-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

二叉搜索树

解决这个问题需要找到一组满足以下条件的 $i$ 和 $j$：

$\bigl| i-j \bigr| \le k$

$\bigl| \mathrm{nums}[i] - \mathrm{nums}[j] \bigr| \le t$

我们把大于等于 $x$ 的最小的数 $s$ 当做 $x$ 在 BST 中的后继节点。同样的，我们能把小于等于 $x$ 最大的数 $g$ 当做 $x$ 在 BST 中的前继节点。$s$ 和 $g$ 这两个数是距离 $x$ 最近的数。因此只需要检查它们和 $x$ 的距离就能知道条件2是否满足了。

class Solution{
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    TreeSet<Long> set = new TreeSet<>();
    for (int i = 0; i < nums.length; ++i) {
        // Find the successor of current element
        Long s = set.ceiling((long)nums[i]);
        if (s != null && s <= nums[i] + t) return true;

        // Find the predecessor of current element
        Long g = set.floor((long)nums[i]);
        if (g != null && nums[i] <= g + t) return true;

        set.add((long)nums[i]);
        if (set.size() > k) {
            set.remove((long)nums[i - k]);
        }
    }
    return false;
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/contains-duplicate-iii/solution/cun-zai-zhong-fu-yuan-su-iii-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}

时间复杂度：$O(n \log (\min(n,k)))$
我们需要遍历这个 $n$ 长度的数组。对于每次遍历，在 BST 中搜索，插入 或者 删除 都需要花费 $O(\log \min(k, n))$ 的时间。

空间复杂度：$O(\min(n,k))$
空间复杂度由 BST 的大小决定，其大小的上限由 $k$ 和 $n$ 共同决定。

桶排序

利用桶将数字分组，每个一数字 $x$ 要想找到与 $x$ 大小相邻（小于t）并且位置相邻（小于k）的元素，只需要判断相邻的桶中的元素的大小是否相邻（小于t）并且位置是否相邻（小于k）。通过使用桶减小了之间的距离

public class Solution {
    // Get the ID of the bucket from element value x and bucket width w
    // In Java, `-3 / 5 = 0` and but we need `-3 / 5 = -1`.
    private long getID(long x, long w) {
        return x < 0 ? (x + 1) / w - 1 : x / w;
    }

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (t < 0) return false;
        Map<Long, Long> d = new HashMap<>();
        long w = (long)t + 1;
        for (int i = 0; i < nums.length; ++i) {
            long m = getID(nums[i], w);
            // check if bucket m is empty, each bucket may contain at most one element
            if (d.containsKey(m))
                return true;
            // check the nei***or buckets for almost duplicate
            if (d.containsKey(m - 1) && Math.abs(nums[i] - d.get(m - 1)) < w)
                return true;
            if (d.containsKey(m + 1) && Math.abs(nums[i] - d.get(m + 1)) < w)
                return true;
            // now bucket m is empty and no almost duplicate in nei***or buckets
            d.put(m, (long)nums[i]);
            if (i >= k) d.remove(getID(nums[i - k], w));
        }
        return false;
    }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/contains-duplicate-iii/solution/cun-zai-zhong-fu-yuan-su-iii-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。