Сложность: 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 {
private long getID(long x, long w) {
return Math.floorDiv(x, w);
}
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (t < 0) return false;
Map<Long, Long> buckets = new HashMap<>();
long w = (long) t + 1;
for (int i = 0; i < nums.length; ++i) {
long bucket = getID(nums[i], w);
if (buckets.containsKey(bucket)) return true;
if (
buckets.containsKey(bucket - 1) &&
Math.abs(nums[i] - buckets.get(bucket - 1)) < w
) return true;
if (
buckets.containsKey(bucket + 1) &&
Math.abs(nums[i] - buckets.get(bucket + 1)) < w
) return true;
buckets.put(bucket, (long) nums[i]);
if (i >= k) buckets.remove(getID(nums[i - k], w));
}
return false;
}
}Ставь 👍 и забирай 📚 Базу знаний