0220. 存在重复元素 III

0220. 存在重复元素 III #

  • 标签:排序、有序集合、哈希表
  • 难度:中等

题目大意 #

描述:给定一个整数数组 nums,以及两个整数 kt

要求:判断数组中是否存在两个不同下标的 ij,其对应元素满足 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
3
4
5
6
输入nums = [1,2,3,1], k = 3, t = 0
输出True


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

解题思路 #

题目中需要满足两个要求,一个是元素值的要求(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:桶排序 #

  1. 利用桶排序的思想,将桶的大小设置为 t + 1。只需要使用一重循环遍历位置 i,然后根据 nums[i] // (t + 1),从而决定将 nums[i] 放入哪个桶中。
  2. 这样在同一个桶内各个元素之间的差值绝对值都小于等于 t。而相邻桶之间的元素,只需要校验一下两个桶之间的差值是否不超过 t。这样就可以以 $O(1)$ 的时间复杂度检测相邻 2 * k 个元素是否满足 abs(nums[i] - nums[j]) <= t
  3. abs(i - j) <= k 条件则可以通过在一重循环遍历时,将超出范围的 nums[i - k] 从对应桶中删除,从而保证桶中元素一定满足 abs(i - j) <= k

具体步骤如下:

  1. 将每个桶的大小设置为 t + 1。我们将元素按照大小依次放入不同的桶中。
  2. 遍历数组 nums 中的元素,对于元素 nums[i]
    1. 如果 nums[i] 放入桶之前桶里已经有元素了,那么这两个元素必然满足 abs(nums[i] - nums[j]) <= t
    2. 如果之前桶里没有元素,那么就将 nums[i] 放入对应桶中。
    3. 再判断左右桶的左右两侧桶中是否有元素满足 abs(nums[i] - nums[j]) <= t
    4. 然后将 nums[i - k] 之前的桶清空,因为这些桶中的元素与 nums[i] 已经不满足 abs(i - j) <= k 了。
  3. 最后上述满足条件的情况就返回 True,最终遍历完仍不满足条件就返回 False

思路 1:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        bucket_dict = dict()
        for i in range(len(nums)):
            # 将 nums[i] 划分到大小为 t + 1 的不同桶中
            num = nums[i] // (t + 1)

            # 桶中已经有元素了
            if num in bucket_dict:
                return True

            # 把 nums[i] 放入桶中
            bucket_dict[num] = nums[i]

            # 判断左侧桶是否满足条件
            if (num - 1) in bucket_dict and abs(bucket_dict[num - 1] - nums[i]) <= t:
                return True
            # 判断右侧桶是否满足条件
            if (num + 1) in bucket_dict and abs(bucket_dict[num + 1] - nums[i]) <= t:
                return True
            # 将 i - k 之前的旧桶清除,因为之前的桶已经不满足条件了
            if i >= k:
                bucket_dict.pop(nums[i - k] // (t + 1))

        return False

思路 1:复杂度分析 #

  • 时间复杂度:$O(n)$。$n$ 是给定数组长度。
  • 空间复杂度:$O(min(n, k))$。桶中最多包含 $min(n, k + 1)$ 个元素。

思路 2:滑动窗口(固定长度) #

  1. 使用一个长度为 k 的滑动窗口,每次遍历到 nums[right] 时,滑动窗口内最多包含 nums[right] 之前最多 k 个元素。只需要检查前 k 个元素是否在 [nums[right] - t, nums[right] + t] 区间内即可。
  2. 检查 k 个元素是否在 [nums[right] - t, nums[right] + t] 区间,可以借助保证有序的数据结构(比如 SortedList)+ 二分查找来解决,从而减少时间复杂度。

具体步骤如下:

  1. 使用有序数组类 window 维护一个长度为 k 的窗口,满足数组内元素有序,且支持增加和删除操作。
  2. leftright 都指向序列的第一个元素。即:left = 0right = 0
  3. 将当前元素填入窗口中,即 window.add(nums[right])
  4. 当窗口元素大于 k 个时,即 right - left > k,移除窗口最左侧元素,并向右移动 left
  5. 当窗口元素小于等于 k 个时:
    1. 使用二分查找算法,查找 nums[right]window 中的位置 idx
    2. 判断 window[idx] 与相邻位置上元素差值绝对值,若果满足 abs(window[idx] - window[idx - 1]) <= t 或者 abs(window[idx + 1] - window[idx]) <= t 时返回 True
  6. 向右移动 right
  7. 重复 3 ~ 6 步,直到 right 到达数组末尾,如果还没找到满足条件的情况,则返回 False

思路 2:代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from sortedcontainers import SortedList

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        size = len(nums)
        window = SortedList()
        left, right = 0, 0
        while right < size:
            window.add(nums[right])
            
            if right - left > k:
                window.remove(nums[left])
                left += 1
            
            idx = bisect.bisect_left(window, nums[right])
            
            if idx > 0 and abs(window[idx] - window[idx - 1]) <= t:
                return True
            if idx < len(window) - 1 and abs(window[idx + 1] - window[idx]) <= t:
                return True

            right += 1

        return False

思路 2:复杂度分析 #

  • 时间复杂度:$O(n \times \log_2(min(n, k)))$。
  • 空间复杂度:$O(min(n, k))$。

参考资料 #

本站总访问量  次  |  您是本站第  位访问者