Начиная со второго дня наших 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 дней кодирования». Надеюсь, вам понравится наш медленный и неуклонный подход.