Содержит дубликат III

Проблема

Дан целочисленный массив nums и два целых числа k и t, вернуть истину, если в массиве есть два различных индекса i и j, такие что abs (nums [i] - nums [j]) ‹= t и abs (i - j) ‹= K.

Пример 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Пример 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Пример 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Подсказка №1

Сложность времени O (n log k) - это укажет, что сортировка задействована для k элементов.

Подсказка 2

Используйте уже существующее состояние для оценки следующего состояния. Например, набор из k отсортированных чисел нужен только для отслеживания. Когда мы обрабатываем следующее число в массиве, мы можем использовать существующее отсортированное состояние, и нет необходимости снова сортировать следующий перекрывающийся набор из k чисел.

Давайте начнем

Как обычно, наша основная цель - решить проблему и в то же время добиться максимальной временной сложности с минимальной пространственной сложностью. Если вы новичок в решении проблем или пытаетесь решить проблемы со структурой данных, я предлагаю вам начать с подхода грубой силы, а затем попытаться оптимизировать свое решение до наилучшей временной / пространственной сложности.

Анализ

Прежде чем переходить к решению или псевдокоду, прочтите несколько раз формулировку проблемы и убедитесь, что вы хорошо ее поняли.
Основываясь на постановке задачи, мы понимаем, что нам нужно найти два различных индекса i и j, таких что abs (nums [i] - nums [j]) ‹= t и abs (i - j)‹ = k.
На этот раз проблема умеренная и не такая простая, как предыдущая. Итак, я воспользуюсь предоставленными подсказками. Я поделился двумя подсказками, связанными с проблемой.
Основываясь на первом указании, понятно, что нам нужно сначала отсортировать элементы, а затем, используя отсортированный список, нам нужно найти, есть ли два разных индекса, то есть удовлетворяющих предоставленному условию.
С помощью сортировки и перебора всех элементов массива мы можем достичь решения за O (n log k) сложность.
С помощью второй подсказки мы поняли, что нам нужно поддерживать отсортированные элементы с их состоянием в структуре данных таким образом, чтобы нам не приходилось снова сортировать следующие перекрывающиеся элементы.
Из пунктов с №4 по №6 мы определенно можем выбрать TreeSet (структура данных в Java), который будет лучшим кандидатом для решения этой проблемы.
И со всеми этими пунктами мы также получили подсказку, что эта проблема подпадает под «шаблон скользящего окна».

Скользящее окно - это подсписок или подмассив, который выполняется поверх базовой структуры данных. Структура данных является повторяемой и упорядоченной, например массив или строка. На высоком уровне это можно рассматривать как подмножество метода двух указателей.

TreeSet в Java

TreeSet - это отсортированная коллекция, которая расширяет класс AbstractSet и реализует интерфейс NavigableSet.

В нем хранятся уникальные элементы
Не сохраняет порядок вставки элементов.
Сортирует элементы в порядке возрастания.
Это не потокобезопасный

В нашем решении мы в основном будем использовать два следующих важных метода Tree Set.

потолок () = ›Этот метод возвращает наименьший элемент в этом наборе, который больше или равен данному элементу, или null, если такого элемента нет.
floor () = ›Этот метод возвращает самый большой элемент в этом наборе, меньший или равный данному элементу, или null, если такого элемента нет.

Итак, со всеми этими подсказками и анализом, давайте начнем писать наш алгоритм или псевдокод.

Алгоритм | Псевдокод

Создайте TreeSet для хранения посещенных или отслеживаемых элементов в массиве.
Итерируйте каждый элемент в массиве и получите следующие два значения
low = ›самый высокий элемент в наборе, меньший, чем текущий элемент nums [i]
hight = ›наименьший элемент в наборе больше, чем текущий элемент nums [i]
if ((low! = null && (long) nums [i] - low ‹= t) || (high! = null && (long) high - nums [i]‹ = t)) return true
Это Значит, мы нашли два индекса, удовлетворяющих требуемым условиям.
если условия не выполняются, вставьте текущий элемент nums [i] в treeSet отслеживания.
если мы дойдем до (i ›= k) элемента, мы можем удалить первый элемент, поскольку два индекса, которые нам нужно идентифицировать, должны находиться в пределах‹ = k индексов.

Приступим к написанию решения.

Перебрать элементы в массиве. Если мы найдем два индекса, которые соответствуют требуемому условию, сравнив низкие и высокие значения в treeSet. Вот и все. Это наш ответ.
Данный массив содержит дубликаты!

Решение (на Java)

class Solution {
        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Integer> visitedSet = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            Integer low = visitedSet.floor(nums[i]);
            Integer high = visitedSet.ceiling(nums[i]);
            if ((low != null && (long) nums[i] - low <= t) || (high != null && (long) high - nums[i] <= t)) {
                return true;
            }
            visitedSet.add(nums[i]);
            if (i >= k) {
                visitedSet.remove(nums[i - k]);
            }
        }
        return false;
    }
    }

Сложность

Сложность времени = ›O (n log k)
Сложность пространства =› O (k)

Заключение

Эта проблема - очень хороший пример шаблона скользящего окна. Ознакомьтесь с другими примерами в этой категории для дальнейшего изучения. Поскольку сложность нашего решения составляет O (n log k), это не лучшее оптимизированное решение. Основываясь на моем исследовании и анализе, я обнаружил, что мы можем достичь сложности O (n) для этой проблемы, используя сортировку по корзине. Но это немного сложное решение, основанное на моем понимании. Поэтому я предоставляю читателям этой статьи попробовать в качестве упражнения решение для сортировки по ведру O (n). Если интересно, поделитесь своим опытом решения этой проблемы в O (n) сложности в разделе комментариев этой статьи. Давайте учиться друг у друга.

использованная литература

Проблема LeetCode в этой статье:

Https://leetcode.com/explore/challenge/card/september-leetcoding-challenge/554/week-1-september-1st-september-7th/3446/

Спасибо, что прочитали этот пост!

Я надеюсь, что эта статья будет в какой-то мере информативной и полезной. Если да, поставьте лайк и поделитесь! Следуйте за мной в Twitter | LinkedIn для связанного контента.

Удачного обучения!

Первоначально опубликовано на https://geetcloud.blogspot.com 3 сентября 2021 г.

Содержит дубликат III