Начиная со второго дня наших 30 дней программирования, мы обновляем концепцию метода двух указателей, чтобы помочь нам решить проблемы сортировки в массиве за линейное время.
Если вы еще не читали предыдущие части блога, предлагаю начать с День 1 — Алгоритм скользящего окна.
Подход с двумя указателями — неотъемлемая часть инструментария программиста, особенно на технических собеседованиях. Имя в данном случае справедливо, оно предполагает использование двух указателей для экономии времени и места. (Здесь указатели в основном являются индексами массива).
Точно так же, как бинарный поиск — это оптимизация количества попыток, необходимых для достижения результата, этот подход используется для той же пользы.
Идея состоит в том, чтобы одновременно перебирать две разные части массива, чтобы получить ответ быстрее.
Когда использовать метод двух указателей?
Ниже приведены некоторые основные подсказки для выявления такой проблемы:
- Проблема будет основываться на структуре данных массива, строки или списка.
- Вашей целью будет определение пары данных или сортировка данных внутри массива за линейное время.
- Это применимо только к конечному набору данных, то есть к конечному массиву.
Алгоритм двух указателей
Вот несколько формулировок проблемы, которые пытаются решить с помощью метода двух указателей:
Возведение отсортированного массива в квадрат
Учитывая целочисленный массив, nums отсортированный в неубывающем порядке, возвращает массив квадратов каждого числа, отсортированного в неубывающем порядке.
Пример 1:
Ввод: nums = [-4,-1,0,3,10]
Вывод: [0,1,9,16,100]
Объяснение: после возведения в квадрат массив становится [16,1,0,9,100].
После сортировки становится [0,1,9,16,100].
Пример 2:
Ввод: nums = [-7,-3,2,3,11]
Вывод: [4,9,9,49,121]
Проблема национального флага Нидерландов
Задача о голландском национальном флаге (DNF) — одна из самых популярных задач программирования, предложенная Эдсгером Дейкстрой. Флаг Нидерландов состоит из трех цветов: белого, красного и синего.
Задача состоит в том, чтобы случайно расположить шары белого, красного и синего цветов так, чтобы шары одного цвета оказались вместе.
Рассмотрим эту проблему на массиве; задача состоит в том, чтобы отсортировать массивы 0, 1 и 2 за линейное время без дополнительного пространства. Поскольку массив проходится только один раз, временная сложность приведенного ниже алгоритма составляет O (n).
Минимальное окно сортировки
Учитывая целочисленный массив nums, вам нужно найти один непрерывный подмассив, который, если вы только отсортируете этот подмассив в порядке возрастания, то весь массив будет отсортирован в порядке возрастания.
Верните кратчайший такой подмассив и выведите его длину.
Пример 1:
Если входной массив равен [10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60], ваша программа должна определить, что подмассив находится между индексами 3 и 8.
Пример 2:
Если входной массив равен [0, 1, 15, 25, 6, 7, 30, 40, 50], ваша программа должна найти, что подмассив находится между индексами 2 и 5.
Пара чисел, сумма которых равна K
Учитывая отсортированный массив целых чисел, найдите пару чисел, сумма которых равна K, имея в виду, что обход не может превышать O (n).
Техника двух указателей чрезвычайно известна, когда речь идет о соревновательном программировании, а также о взломах интервью.
Приведенный выше метод не только возвращает правильное значение, но и решает большинство проблем с массивами за линейное время. Это немалый подвиг, учитывая, что большинство этих алгоритмов обычно решаются за O(n²) с использованием алгоритмов грубой силы.
На этом заканчивается содержание второго дня нашей серии «30 дней кодирования». Надеюсь, вам понравится наш медленный и неуклонный подход.