Leetcode220.存在重复元素 III

题目描述

给定一个整数数组，判断数组中是否有两个不同的索引i和j，使得nums[i]和nums[j]的差的绝对值最大为t，并且i和j之间的差的绝对值最大为k。

示例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

题解源自官方：https://leetcode-cn.com/problems/contains-duplicate-iii/solution/cun-zai-zhong-fu-yuan-su-iii-by-leetcode/

方法一（线性搜索）【超时】

思路

将每个元素与它之前的 kk 个元素比较，查看它们的数值之差是不是在 t 以内。

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;

复杂度分析

• 时间复杂度：O(nmin(k,n)) 每次搜索都将花费 O(min(k,n)) 的时间，需要注意的是一次搜索中我们最多比较 n 次，哪怕 k 比 n 大。
• 空间复杂度：O(1) 额外开辟的空间为常数个。

方法二 （二叉搜索树）【通过】

思路

• 如果窗口中维护的元素是有序的，只需要用二分搜索检查条件二是否是满足的就可以了。
• 利用自平衡二叉搜索树，可以在对数时间内通过插入和删除来对滑动窗口内元素排序。

算法

方法一真正的瓶颈在于检查第二个条件是否满足需要扫描滑动窗口中所有的元素。因此我们需要考虑的是有没有比全扫描更好的方法。

如果窗口内的元素是有序的，那么用两次二分搜索就可以找到 x+t 和 x−t 这两个边界值了。

然而不幸的是，窗口中的元素是无序的。这里有一个初学者非常容易犯的错误，那就是将滑动窗口维护成一个有序的数组。虽然在有序数组中搜索只需要花费对数时间，但是为了让数组保持有序，我们不得不做插入和删除的操作，而这些操作是非常不高效的。想象一下，如果你有一个kk大小的有序数组，当你插入一个新元素x的时候。虽然可以在O(logk)时间内找到这个元素应该插入的位置，但最后还是需要O(k)的时间来将x插入这个有序数组。因为必须得把当前元素应该插入的位置之后的所有元素往后移一位。当你要删除一个元素的时候也是同样的道理。在删除了下标为i的元素之后，还需要把下标i之后的所有元素往前移一位。因此，这种做法并不会比方法一更好。

为了能让算法的效率得到真正的提升，我们需要引入一个支持插入，搜索，删除操作的动态数据结构，那就是自平衡二叉搜索树。自平衡这个词的意思是，这个树在随机进行插入，删除操作之后，它会自动保证树的高度最小。为什么一棵树需要自平衡呢？这是因为在二叉搜索树上的大部分操作需要花费的时间跟这颗树的高度直接相关。可以看一下下面这棵严重左偏的非平衡二叉搜索树。

image.png
在上面这棵二叉搜索树上查找一个元素需要花费 线性 时间复杂度，这跟在链表中搜索的速度是一样的。现在我们来比较一下下面这棵平衡二叉搜索树。
image.png
假设这棵树上节点总数为n，一个平衡树能把高度维持在h=logn。因此这棵树上支持在O(h)=O(logn)时间内完成插入，搜索，删除操作。
下面给出整个算法的伪代码：

• 初始化一棵空的二叉搜索树set
• 对于每个元素x，遍历整个数组
  -- 在set上查找大于等于x的最小的数，如果s-x≤t则返回true
  -- 在set上查找小于等于x的最大的数，如果x−g≤t则返回true
  -- 在set中插入x
  -- 如果树的大小超过了k, 则移除最早加入树的那个数。
• 返回false
  我们把大于等于x的最小的数s当做x在 BST 中的后继节点。同样的，我们能把小于等于x最大的数g当做x在 BST 中的前继节点。s和g这两个数是距离x最近的数。因此只需要检查它们和x的距离就能知道条件二是否满足了。

public Boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t){
    TreeSet<Integer> set = new TreeSet<>();
    for(int i=0; i<nums.length; ++i){
        //Find the successor of current element
        Integer s = set.ceiling(nums[i]);
        if(s != null && s <= nums[i]+t)
            return true;
        
        //Find the predecessor of current element
        Integer g = set.floor(nums[i]);
        if(g != null && nums[i] <= g + t)
            return true;
        
        set.add(nums[i]);
        if (set.size() > k){
            set.remove(nums[i-k]);
        }
    }
    return false;
}

复杂度分析

• 时间复杂度：O(nlog(min(n,k)))我们需要遍历这个n长度的数组。对于每次遍历，在 BST 中 搜索，插入或者删除都需要花费O(logmin(k,n))的时间。
• 空间复杂度：O(min(n,k))空间复杂度由 BST 的大小决定，其大小的上限由k和n共同决定。

笔记

当数组中的元素非常大的时候，进行数学运算可能造成溢出。所以可以考虑使用支持大数的数据类型，例如 long。
C++ 中的std::set，std::set::upper_bound和std::set::lower_bound分别等价于 Java 中的TreeSet，TreeSet::ceiling和TreeSet::floor。Python 标准库不提供自平衡 BST。

方法三（桶）【通过】

思路

受桶排序的启发，我们可以把桶当做窗口来实现一个线性复杂度的解法。

算法

桶排序是一种把元素分散到不同桶中的排序算法。接着把每个桶再独立地用不同的排序算法进行排序。
回到这个问题，我们尝试去解决的最大的问题在于：

1.对于给定的元素x, 在窗口中是否有存在区间 [x−t,x+t] 内的元素？
2.我们能在常量时间内完成以上判断嘛？

我们不妨把把每个元素当做一个人的生日来考虑一下吧。假设你是班上新来的一位学生，你的生日在 三月 的某一天，你想知道班上是否有人生日跟你生日在t=30天以内。在这里我们先假设每个月都是30天，很明显，我们只需要检查所有生日在 二月，三月，四月 的同学就可以了。

之所以能这么做的原因在于，我们知道每个人的生日都属于一个桶，我们把这个桶称作月份！每个桶所包含的区间范围都是t，这能极大的简化我们的问题。很显然，任何不在同一个桶或相邻桶的两个元素之间的距离一定是大于t的。

我们把上面提到的桶的思想应用到这个问题里面来，我们设计一些桶，让他们分别包含区间...,[0,t],[t+1,2t+1],...。我们把桶来当做窗口，于是每次我们只需要检查x所属的那个桶和相邻桶中的元素就可以了。终于，我们可以在常量时间解决在窗口中搜索的问题了。

还有一件值得注意的事，这个问题和桶排序的不同之处在于每次我们的桶里只需要包含最多一个元素就可以了，因为如果任意一个桶中包含了两个元素，那么这也就是意味着这两个元素是 足够接近的 了，这时候我们就直接得到答案了。因此，我们只需使用一个标签为桶序号的散列表就可以了。

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

复杂度分析

• 时间复杂度：O(n)
  对于这 n 个元素中的任意一个元素来说，我们最多只需要在散列表中做三次 搜索，一次 插入 和一次 删除。这些操作是常量时间复杂度的。因此，整个算法的时间复杂度为 O(n)。
• 空间复杂度：-O(min(n,k))
  需要开辟的额外空间取决了散列表的大小，其大小跟它所包含的元素数量成线性关系。散列表的大小的上限同时由 n 和 k 决定。因此，空间复杂度为 O(min(n,k))。