1. Обзор
В этом уроке мы обсудим подход с двумя указателями для решения проблем, связанных с массивами и списками. Этот метод является простым и эффективным способом повышения производительности нашего алгоритма.
2. Описание техники
Во многих задачах, связанных с массивами или списками, мы должны анализировать каждый элемент массива по сравнению с другими его элементами.
Чтобы решить подобные проблемы, мы обычно начинаем с первого индекса и перебираем массив один или несколько раз в зависимости от нашей реализации. Иногда нам также приходится создавать временный массив в зависимости от требований нашей проблемы.
Вышеприведенный подход может дать нам правильный результат, но, скорее всего, он не даст нам наиболее эффективного с точки зрения пространства и времени решения.
В результате часто полезно подумать, можно ли эффективно решить нашу проблему с помощью подхода с двумя указателями .
При подходе с двумя указателями указатели ссылаются на индексы массива. Используя указатели, мы можем обрабатывать два элемента в цикле, а не только один.
Общие закономерности в подходе с двумя указателями включают в себя:
- Два указателя каждый, начиная с начала и до конца, пока они оба не встретятся
- Один указатель движется в медленном темпе, в то время как другой указатель движется в более быстром темпе
Оба вышеперечисленных паттерна могут помочь нам уменьшить временную и пространственную сложность наших проблем, поскольку мы получаем ожидаемый результат за меньшее количество итераций и без использования слишком большого дополнительного пространства.
Теперь давайте рассмотрим несколько примеров, которые помогут нам немного лучше понять эту технику.
3. Сумма существует в массиве
Проблема: Учитывая сортированный массив целых чисел, нам нужно посмотреть, есть ли в нем два числа, сумма которых равна определенному значению.
Например, если наш входной массив [1, 1, 2, 3, 4, 6, 8, 9] и целевое значение 11 , тогда наш метод должен возвращать true . Однако, если целевое значение 20 , он должен вернуть false .
Давайте сначала посмотрим на наивное решение:
public boolean twoSumSlow(int[] input, int targetValue) {
for (int i = 0; i < input.length; i++) {
for (int j = 1; j < input.length; j++) {
if (input[i] + input[j] == targetValue) {
return true;
}
}
}
return false;
}В приведенном выше решении мы дважды перебирали входной массив, чтобы получить все возможные комбинации. Мы сверили сумму комбинации с целевым значением и вернули true , если она совпадает. Временная сложность этого решения равна O(n^2) .
Теперь давайте посмотрим, как мы можем применить здесь метод двух указателей:
public boolean twoSum(int[] input, int targetValue) {
int pointerOne = 0;
int pointerTwo = input.length - 1;
while (pointerOne < pointerTwo) {
int sum = input[pointerOne] + input[pointerTwo];
if (sum == targetValue) {
return true;
} else if (sum < targetValue) {
pointerOne++;
} else {
pointerTwo--;
}
}
return false;
}Поскольку массив уже отсортирован, мы можем использовать два указателя. Один указатель начинается с начала массива, а другой указатель начинается с конца массива, а затем мы добавляем значения в эти указатели. Если сумма значений меньше целевого значения, мы увеличиваем левый указатель, а если сумма больше целевого значения, мы уменьшаем правый указатель.
Мы продолжаем перемещать эти указатели до тех пор, пока не получим сумму, соответствующую целевому значению, или мы не достигнем середины массива, и никакие комбинации не будут найдены. Временная сложность этого решения составляет O(n) и пространственная сложность составляет O(1) , значительное улучшение по сравнению с нашей первой реализацией.
4. Поверните Массив k Шагов
Проблема: Учитывая массив, поверните массив вправо на k шагов, где k неотрицательно. Например, если наш входной массив [1, 2, 3, 4, 5, 6, 7] и k есть 4 , то выход должен быть [4, 5, 6, 7, 1, 2, 3] .
Мы можем решить эту проблему, снова имея два цикла, которые сделают временную сложность O(n^2) или используя дополнительный временный массив, но это сделает пространственную сложность O(n) .
Давайте решим эту проблему, используя вместо этого метод двух указателей:
public void rotate(int[] input, int step) {
step %= input.length;
reverse(input, 0, input.length - 1);
reverse(input, 0, step - 1);
reverse(input, step, input.length - 1);
}
private void reverse(int[] input, int start, int end) {
while (start < end) {
int temp = input[start];
input[start] = input[end];
input[end] = temp;
start++;
end--;
}
}В приведенных выше методах мы несколько раз меняем местами разделы входного массива, чтобы получить требуемый результат. Для реверсирования секций мы использовали подход с двумя указателями, при котором замена элементов производилась на обоих концах секции массива.
В частности, мы сначала перевернем все элементы массива. Затем мы перевернем первые элементы k , а затем перевернем остальные элементы. Временная сложность этого решения равна O(n) и пространственная сложность равна O(1) .
5. Средний элемент в связанном списке
Проблема: Учитывая один LinkedList , найдите его средний элемент. Например, если наш ввод LinkedList 1->2->3->4->5, тогда вывод должен быть 3 .
Мы также можем использовать метод двух указателей в других структурах данных, подобных массивам, таким как Связанный список :
publicT findMiddle(MyNode head) { MyNode slowPointer = head; MyNode fastPointer = head; while (fastPointer.next != null && fastPointer.next.next != null) { fastPointer = fastPointer.next.next; slowPointer = slowPointer.next; } return slowPointer.data; }
В этом подходе мы проходим по связанному списку, используя два указателя. Один указатель увеличивается на один, а другой-на два. Когда быстрый указатель достигнет конца, медленный указатель будет находиться в середине связанного списка. Временная сложность этого решения равна O(n) , а пространственная сложность равна O(1) .
6. Заключение
В этой статье мы обсудили, как мы можем применить метод двух указателей, просмотрев некоторые примеры, и рассмотрели, как он повышает эффективность нашего алгоритма.
Код в этой статье доступен на Github .