0220. 存在重复元素 III #
- 标签:排序、有序集合、哈希表
- 难度:中等
题目大意 #
描述:给定一个整数数组 nums
,以及两个整数 k
、t
。
要求:判断数组中是否存在两个不同下标的 i
和 j
,其对应元素满足 abs(nums[i] - nums[j]) <= t
,同时满足 abs(i - j) <= k
。如果满足条件则返回 True
,不满足条件返回 False
。
说明:
- $0 \le nums.length \le 2 * 10^4$。
- $-2^{31} \le nums[i] \le 2^{31} - 1$。
- $0 \le k \le 10^4$。
- $0 \le t \le 2^{31} - 1$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
题目中需要满足两个要求,一个是元素值的要求(abs(nums[i] - nums[j]) <= t
) ,一个是下标范围的要求(abs(i - j) <= k
)。
对于任意一个位置 i
来说,合适的 j
应该在区间 [i - k, i + k]
内,同时 nums[j]
值应该在区间 [nums[i] - t, nums[i] + t]
内。
最简单的做法是两重循环遍历数组,第一重循环遍历位置 i
,第二重循环遍历 [i - k, i + k]
的元素,判断是否满足 abs(nums[i] - nums[j]) <= t
。但是这样做的时间复杂度为 $O(n \times k)$,其中 $n$ 是数组 nums
的长度。
我们需要优化一下检测相邻 2 * k
个元素是否满足 abs(nums[i] - nums[j]) <= t
的方法。有两种思路:「桶排序」和「滑动窗口(固定长度)」。
思路 1:桶排序 #
- 利用桶排序的思想,将桶的大小设置为
t + 1
。只需要使用一重循环遍历位置i
,然后根据nums[i] // (t + 1)
,从而决定将nums[i]
放入哪个桶中。 - 这样在同一个桶内各个元素之间的差值绝对值都小于等于
t
。而相邻桶之间的元素,只需要校验一下两个桶之间的差值是否不超过t
。这样就可以以 $O(1)$ 的时间复杂度检测相邻2 * k
个元素是否满足abs(nums[i] - nums[j]) <= t
。 - 而
abs(i - j) <= k
条件则可以通过在一重循环遍历时,将超出范围的nums[i - k]
从对应桶中删除,从而保证桶中元素一定满足abs(i - j) <= k
。
具体步骤如下:
- 将每个桶的大小设置为
t + 1
。我们将元素按照大小依次放入不同的桶中。 - 遍历数组
nums
中的元素,对于元素nums[i]
:- 如果
nums[i]
放入桶之前桶里已经有元素了,那么这两个元素必然满足abs(nums[i] - nums[j]) <= t
, - 如果之前桶里没有元素,那么就将
nums[i]
放入对应桶中。 - 再判断左右桶的左右两侧桶中是否有元素满足
abs(nums[i] - nums[j]) <= t
。 - 然后将
nums[i - k]
之前的桶清空,因为这些桶中的元素与nums[i]
已经不满足abs(i - j) <= k
了。
- 如果
- 最后上述满足条件的情况就返回
True
,最终遍历完仍不满足条件就返回False
。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。$n$ 是给定数组长度。
- 空间复杂度:$O(min(n, k))$。桶中最多包含 $min(n, k + 1)$ 个元素。
思路 2:滑动窗口(固定长度) #
- 使用一个长度为
k
的滑动窗口,每次遍历到nums[right]
时,滑动窗口内最多包含nums[right]
之前最多k
个元素。只需要检查前k
个元素是否在[nums[right] - t, nums[right] + t]
区间内即可。 - 检查
k
个元素是否在[nums[right] - t, nums[right] + t]
区间,可以借助保证有序的数据结构(比如SortedList
)+ 二分查找来解决,从而减少时间复杂度。
具体步骤如下:
- 使用有序数组类
window
维护一个长度为k
的窗口,满足数组内元素有序,且支持增加和删除操作。 left
、right
都指向序列的第一个元素。即:left = 0
,right = 0
。- 将当前元素填入窗口中,即
window.add(nums[right])
。 - 当窗口元素大于
k
个时,即right - left > k
,移除窗口最左侧元素,并向右移动left
。 - 当窗口元素小于等于
k
个时:- 使用二分查找算法,查找
nums[right]
在window
中的位置idx
。 - 判断
window[idx]
与相邻位置上元素差值绝对值,若果满足abs(window[idx] - window[idx - 1]) <= t
或者abs(window[idx + 1] - window[idx]) <= t
时返回True
。
- 使用二分查找算法,查找
- 向右移动
right
。 - 重复
3
~6
步,直到right
到达数组末尾,如果还没找到满足条件的情况,则返回False
。
思路 2:代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(n \times \log_2(min(n, k)))$。
- 空间复杂度:$O(min(n, k))$。