leetcode-220
220. 存在重复元素 III
给你一个整数数组 nums
和两个整数 k
和 t
。请你判断是否存在 两个不同下标 i
和 j
,使得 abs(nums[i] - nums[j]) <= t
,同时又满足 abs(i - j) <= k
。
如果存在则返回 true
,不存在返回 false
。
示例:
1 | 输入:nums = [1,2,3,1], k = 3, t = 0 |
解法
解法一:暴力解法
超时
1 | class Solution: |
官方题解一:滑动窗口 + 有序集合
对于序列中每一个元素$x$左侧的最多$k$个元素,如果这$k$个元素中存在一个元素落在区间$[x-t,x+t]$中,我们就找到了一对符合条件的元素。
注意到对于两个相邻的元素,它们各自的左侧的$k$个元素中有$k-1$个重合的。于是我们可以使用滑动窗口的思路,维护一个大小为$k$的滑动窗口,每次遍历到元素$x$时,滑动窗口中包含元素$x$前面的最多$k$个元素,我们检查窗口中是否存在元素落在区间$[x-t,x+t]$即可。
如果使用队列维护滑动窗口内的元素,由于元素是无序的,我们只能对于每个元素都遍历一次队列来检查是否有元素符合条件。如果数组的长度为$n$,则使用队列的时间复杂度为$O(nk)$,会超出时间限制。
因此我们希望能够找到一个数据结构维护滑动窗口内的元素,该数据结构需要满足以下操作:
- 支持添加和删除指定元素的操作,否则我们无法维护滑动窗口;
- 内部元素有序,支持二分查找的操作,这样我们可以快速判断滑动窗口中是否存在元素满足条件,具体而言,对于元素$x$,当我们希望判断滑动窗口中是否存在某个数 $y$ 落在区间$[x-t,x+t]$,只需要判断滑动窗口中所有大于等于 $x-t$ 的元素中是否小于等于 $x+t$即可。
我们可以使用有序集合来支持这些操作。
实现方面,我们在有序集合中查找大于等于$x-t$的最小元素$y$,如果$y$存在,且$y\leq x+t$,我们就找到了一对符合条件的元素。
完成检查后,我们将 $x$ 插入到有序集合中,如果有序集合中元素数量超过了 $k$,我们将有序集合中最早被插入的元素删除即可。
ceiling(E e) 方法返回在这个集合中大于或者等于给定元素的最小元素,如果不存在这样的元素,返回null.
floor(E e)方法返回在这个集合中小于或者等于给定元素的最大元素,如果不存在这样的元素,返回null.
1 | public static boolean containsNearByAlmostDuplicate(int[] nums,int k, int t) { |
官方题解二:桶排序
也可以使用利用桶排序的思想解决本题。我们按照元素的大小进行分桶,维护一个滑动窗口内的元素对应的元素。
对于元素$x$,其影响的区间为 $[ x - t , x + t ]$。故可以设定桶的大小为 $t+1$。
如果两个元素同属一个桶,那么这两个元素必然符合条件。如果两个元素属于相邻桶,那么我们需要校验这两个元素是否差值不超过 $t$。
如果两个元素既不属于同一个桶,也不属于相邻桶,那么这两个元素必然不符合条件。
如果两个不属于相邻桶,说明他们之间的差距已经大于t了
具体地,我们遍历该序列,假设当前遍历到元素 $x$,那么我们首先检查 $x$ 所属于的桶是否已经存在元素,如果存在,那么我们就找到了一对符合条件的元素,否则我们继续检查两个相邻的桶内是否存在符合条件的元素。
实现方面,我们将 $int$ 范围内的每一个整数 $x$ 表示 $x = ( t + 1 ) \times a + b ( 0 \leq b \leq t )$ 的形式,这样$x$ 既归属于编号为$a$的桶。因为一个桶内至多只会有一个元素,所以我们使用哈希表实现即可。
$abs(i-j)\leq k$
$abs(num[i] -num[j])\leq t$
1 | public static boolean containsNearbyAlmostDuplicate2(int[] nums,int k,int t) { |
leetcode-220