Leetcode-220-存在重复元素Ⅲ

发表于 | 分类于

题目

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

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

示例 1:

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

示例 2:

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

示例 3:

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

平衡二叉树/红黑树

Java中的Treeset内部是由红黑树实现的. Treeset.ceiling函数可以寻找特定节点的中序后继, Treeset.floor函数可以寻找特定节点的中序前驱.

  • 初始化一颗空的红黑树tree
  • 遍历整个数组, 对于每一个元素nums[i]:
    • 在tree上查找nums[i]的后继s(大于等于nums[i]的最小的数), 如果s-nums[i]<=t, 则返回true
    • 在tree上查找nums[i]的前驱g(小于等于nums[i]的最大的数), 如果nums[i] - g<=t, 则返回true
    • 在tree中插入nums[i]
    • 如果tree的大小超过了k, 则移除最早加入tree的那个数(nums[i-k])

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Integer> tree = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            Integer s = tree.ceiling(nums[i]); // 寻找当前元素的后继
            Integer g = tree.floor(nums[i]);  // 寻找当前元素的前驱
            
            if (s != null && s <= t + nums[i]) return true;
            if (g != null && nums[i] <= t + g) return true;
            
            tree.add(nums[i]);
            if (tree.size() > k) {
                tree.remove(nums[i - k]);
            }
        }
        return false;
    }
}

image-20200720181700539