Сложность: hard
Вам дан массив целых чисел nums и два целых числа indexDiff и valueDiff.
Найдите пару индексов (i, j) таких, что:
i != j,
abs(i - j) <= indexDiff,
abs(nums[i] - nums[j]) <= valueDiff.
Верните true, если такая пара существует, или false в противном случае.
Пример:
Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0
👨💻 Алгоритм:
1️⃣Инициализация и вычисление корзин:
Рассчитать ширину корзины w = t + 1. Инициализировать пустой хэш-таблицей buckets. Определить функцию getID, которая возвращает идентификатор корзины для элемента x и ширины корзины w.
2️⃣Итерация и проверка корзин:
Перебрать все элементы массива nums. Для каждого элемента nums[i]: Определить его корзину с помощью getID. Проверить, есть ли в текущей корзине элемент. Если есть, вернуть true. Проверить соседние корзины на наличие "почти дубликатов". Если есть, вернуть true. Если текущая корзина пуста и в соседних корзинах нет "почти дубликатов", добавить текущий элемент в соответствующую корзину. Если текущий индекс превышает k, удалить элемент из корзины, которая вышла за пределы окна.
3️⃣Завершение:
Если ни одна пара "почти дубликатов" не найдена, вернуть false.
😎 Решение:
class Solution:
def containsNearbyAlmostDuplicate(self, nums, k, t):
if t < 0: return False
buckets = {}
w = t + 1
for i in range(len(nums)):
bucket = nums[i] // w if nums[i] >= 0 else (nums[i] + 1) // w - 1
if bucket in buckets: return True
if bucket - 1 in buckets and abs(nums[i] - buckets[bucket - 1]) < w: return True
if bucket + 1 in buckets and abs(nums[i] - buckets[bucket + 1]) < w: return True
buckets[bucket] = nums[i]
if i >= k:
del buckets[nums[i - k] // w if nums[i - k] >= 0 else (nums[i - k] + 1) // w - 1]
return False
Ставь 👍 и забирай 📚 Базу знаний