Два указателя — это метод, используемый для решения задач с массивами и строками. Одним из преимуществ использования метода двух указателей является то, что цикл while
никогда не будет иметь более O(n) итераций. В большой нотации O O(n) или линейная сложность описывает производительность алгоритма, время выполнения которого будет расти линейно и прямо пропорционально размеру входных данных.
Техника двух указателей состоит в создании двух целочисленных переменных, которые перемещаются по итерируемому объекту. Эти переменные, обычно называемые i
и j
, представляют собой два индекса массива или входной строки. Существует множество различных способов реализации двух указателей. Мы рассмотрим одну технику в следующем примере.
В этом примере мы перевернем массив, назначив указатели на первый и последний индекс ввода и переместив их друг к другу, пока они не встретятся. С каждой итерацией мы будем писать логику, чтобы переворачивать элементы в массиве, увеличивая один указатель и уменьшая другой.
var arr = [‘h’, ‘e’, ‘l’, ‘l’, ‘o’] const reverseArray = (arr) => { // assign the two pointers to the first and last index let i = 0; let j = arr.length-1; while (i < j) { let tmp = arr[i]; // statement 1 arr[i++] = arr[j]; // statement 2 arr[j--] = tmp; // statement 3 }; return arr; };
Сначала мы присваиваем переменной i
индекс 0
и j
последнему индексу входной строки arr.length-1
. Мы используем i < j
для условия проверки цикла while
. Пока это условие истинно, цикл while будет выполнять свои операторы. Помните, что с while
циклами условие всегда оценивается до выполнения оператора.
Для каждой итерации мы выполняем три оператора:
- Назначьте
tmp
наarr[i]
. Это позволяет нам переназначитьarr[i]
во втором операторе и по-прежнему иметь возможность присвоить исходное значениеarr[i]
arr[j]
. - Присвойте
arr[i]
значениюarr[j]
и увеличьтеi
на 1 - Присвойте
arr[j]
значениюtmp
и уменьшитеj
на 1
Первая итерация в этом примере меняет местами arr[0]
(«h») на arr[3]
(«o»). Вторая итерация меняет местами arr[1]
(«e») на arr[2]
(«l») и так далее. Поскольку мы не создавали новый массив, нам просто нужно вернуть измененный arr
, который был перевернут.
В этом примере функция reverseArray
изменяет исходный массив на месте, что дает нам пространственную сложность O(1). В нотации Big O, сложность пространства O(1) или постоянное пространство означает, что алгоритм использует один и тот же объем памяти независимо от размера входных данных.