题目

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

示例 1:

  1. 输入: nums = [1,2,3,1], k = 3, t = 0
  2. 输出: 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

方案一（滑动窗口+二分搜索）

import heapq
import bisect

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect.bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def getDiff(nums, a):
    '''获取 nums 列表中 与a之差绝对值的最小值
    eg1.
    nums: [1, 2, 3] a: 1 return 0
    eg2.
    nums: [4, 1, 6] a: 3 return 1
    '''
    nums = sorted(nums)
    if a < nums[0]:
        return nums[0] - a
    if a > nums[-1]:
        return a - nums[-1]

    le = find_le(nums, a)
    ge = find_ge(nums, a)

    return ge - a if ge - a < a - le else a - le


class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        if len(nums) <= 1 or k == 0:
            return False

        i, j = 0, 1
        # 扩大窗口阶段
        while j < len(nums) and j < k:
            if getDiff(nums[i:j], nums[j]) <= t:
                return True
            j += 1

        # 扩大阶段已经遍历玩数组
        if j == len(nums):
            return False

        # 平移窗口阶段
        while getDiff(nums[i:j], nums[j]) > t:
            i += 1
            j += 1
            if j >= len(nums):
                return False

        return True
  • leetcode 超时，主要由于每次都需要 sorted 导致时间复杂度过高。

方案二（滑动窗口+自平衡的二叉搜索树）

下面给出整个算法的伪代码：

  • 初始化一颗空的二叉搜索树 bst
  • 对于每个元素 x，遍历整个数组
    • 在 bst 上查找大于等于 x 的最小的数，如果 $s - x \leq ts−x≤t$ 则返回 true
    • 在 bst 上查找小于等于 x 的最大的数，如果$x - g \leq tx−g≤t$ 则返回 true
    • 在 bst 中插入 x
    • 如果树的大小超过了 k, 则移除最早加入树的那个数。
  • 返回 false

由于 python 暂不提供 自平衡的 bst 标准库，所以此处先不实现。

方案三（桶）

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

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

def containsNearbyAlmostDuplicate(nums: [int], k: int, t: int) -> bool:
    if k == 0 or len(nums) <= 1 or t < 0:
        return False

    buckets = {} # key: 桶的 index
    left = 0 # 滑动窗口左侧 index
    for right, num in enumerate(nums):
        bucket_index = num // (t + 1)
        # 超过滑动窗口大小，需去除最前面的桶
        if right - left > k:
            del buckets[nums[left] // (t + 1)]
            left += 1
        # 目标桶中已经有元素了
        if bucket_index in buckets:
            return True
        # 目标桶中没有元素
        buckets[bucket_index] = num
        # 检查相邻桶
        if bucket_index - 1 in buckets and num - buckets[bucket_index - 1] <= t:
            return True
        if bucket_index + 1 in buckets and buckets[bucket_index + 1] - num <= t:
            return True

    return False

分成 t + 1 个桶