В этом алгоритме нет ничего простого

Один из наиболее часто встречающихся алгоритмов - Задача поворота массива:

Для данного массива поверните массив вправо на k шагов, где k неотрицательно. Постарайтесь придумать как можно больше решений - есть как минимум три разных способа решить эту проблему. Не могли бы вы сделать это на месте с O (1) дополнительным пространством?

Например, если вам дали массив [1, 2, 3, 4, 5] и сказали повернуть его 2 шага вправо, результат должен быть [4, 5, 1, 2, 3]. После одного поворота вправо массив будет [5, 1, 2, 3, 4], так что после двух поворота вправо массив станет [4, 5, 1, 2, 3].

На Leetcode эта задача помечена как «легкая» - я не уверен, как они определяют уровень сложности. Однако я думаю, что эта проблема отнюдь не простая. Есть много способов решить эту проблему, отчасти поэтому мне это нравится, и я думаю, что каждое решение сложно по-своему.

В этой статье я рассмотрю три различных подхода к решению этой проблемы:

  1. Выталкивание и отмена сдвига элементов в массиве.
  2. Создание нового массива, в котором элементы начинаются со сдвига.
  3. Переворачивание разных участков массива.

Подход №1: Поппинг и перестановка

При работе с массивами постоянно возникает несколько методов. Один из них - .pop(), который удаляет последний элемент из массива и возвращает этот элемент (подробнее о .pop() здесь). Например:

const arr = [1, 2, 3]
arr.pop() // would return 3
console.log(arr) // would print [1, 2]

Другой распространенный метод, используемый для массивов - .unshift(). Этот метод добавляет один или несколько элементов в начало массива и возвращает новую длину массива (подробнее о .unshift () см. Здесь). Например:

const arr = [2, 3]
arr.unshift(1) // would return 3, the new length of the array
console.log(arr) // would print [1, 2, 3]

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

Например, предположим, что нам даны массивы nums = [1, 2, 3, 4, 5] и k = 2, поэтому мы должны повернуть массив дважды. Используя pop и unshift, мы начнем с выталкивания последнего элемента, 5, что даст nums = [1, 2, 3, 4]. Затем мы отменяем сдвиг 5, помещая его в начало массива, так что nums = [5, 1, 2, 3, 4].

Мы повторяем этот цикл еще раз, снимая 4, делая nums = [5, 1, 2, 3], а затем отменяя сдвиг 4, давая нам окончательный ответ nums = [4, 5, 1, 2, 3].

Кодирование первого подхода

Прежде чем мы начнем кодировать это решение, нужно отметить еще одну вещь по поводу этой проблемы. Допустим, данный массив был [1, 2], и нам сказали повернуть его вправо семь раз. Длина массива меньше семи элементов, поэтому семь раз повернуть его будет нелегко. Итак, прежде чем что-либо делать, как в этом решении, так и в других подходах, мы должны изменить k, используя модуль (%).

Оператор по модулю возвращает остаток от деления одного числа на другое. Например, 10%3 вернет 1, потому что остаток 10/3 равен 1. Точно так же в этой задаче мы хотим установить k равным k % nums.length. В том же примере, если k = 7 и nums = [1, 2], то k = k % nums.length совпадает с k = 7%2 или k = 1. Итак, первая строка этого решения будет такой:

Мы хотим выполнить .pop()и .unshift() столько раз, сколько k равно, поэтому мы создаем цикл for, который повторяется k раз. Внутри цикла for мы сохраняем результат nums.pop() в переменной с именем back. Затем мы отменяем сдвиг back, помещая его в начало массива nums.

Когда цикл for прекращает выполнение, мы возвращаем nums.

Этот первый подход выполняется в линейном времени (O (n)) и постоянном пространстве (O (1)).

Подход # 2: создание нового массива

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

Что произойдет, если предполагается, что элемент переместится в индекс, превышающий длину массива nums? В этом случае вы используете оператор по модулю, вычисляя результат перемещения на новое расстояние % длины массива nums. Я думаю, что это особенно сложная часть этого подхода, поэтому я воспользуюсь примером.

Допустим, вы начали с массива nums = [1, 2, 3] и пустого массива arr. Нам сказали k = 2, поэтому массив переместится на 2 точки вправо. Мы начинаем с перемещения первого элемента массива nums, 1. 1 имеет индекс 0 (i = 0), и мы хотим переместить его на две позиции. Другими словами, мы хотим, чтобы его позиция в массиве arr определялась i + k, который является индексом 2.

Теперь мы находимся в первом индексе массива nums, 2. Мы хотим переместить его на k шагов вправо, но i + k равно 3, и это будет больше, чем длина массива nums. Итак, чтобы найти новое место для 2, мы должны сделать (i + k) % nums.length или 3%3, что равно 0. Итак, мы должны переместить элемент 2 в индекс 0 в arr.

Наконец, мы находимся во втором индексе массива nums, который равен 3. Мы хотим переместить его k шаг вправо, и i + k равно 4, что больше длины массива nums. Итак, чтобы найти новое место для 3, мы должны сделать (i + k) % nums.length или 4%3, то есть 1. Итак, мы должны переместить элемент 3 в индекс 1 в arr, что даст нам окончательный результат этой проблемы.

Кодирование второго подхода

Чтобы начать это решение, мы вносим те же изменения в k, что и в первом подходе. Затем мы инициализируем новый пустой массив с именем arr.

Теперь мы используем цикл for для просмотра каждого элемента в nums. В каждом индексе мы помещаем этот элемент в новое место в arr. Мы можем найти это новое место, выполнив (i + k) % nums.length. Итак, мы устанавливаем arr[(i + k) % nums.length] равным nums[i].

Теперь arr будет повернутым массивом, который нам нужен. Однако в этой проблеме мы должны изменить массив nums, поэтому мы должны установить каждый индекс в nums равным значению этого индекса в arr. Для этого мы создали еще один цикл for. Для каждого индекса мы установим nums[i] равным arr[i]. Когда цикл for завершится, мы можем вернуть nums.

Этот второй подход выполняется в линейном времени (O (n)) и линейном пространстве (O (n)).

Подход № 3: поменять местами разделы

В этом третьем подходе мы изменим части nums. В первый раз мы полностью переворачиваем массив. Во второй раз мы переворачиваем первые k элементов массива. В третий раз мы меняем местами последние элементы массива от k до конца.

Идею, лежащую в основе этого подхода, лучше всего можно увидеть на примере. Мы начинаем с массива [1, 2, 3, 4, 5], и мы хотим повернуть его на два шага. Начнем с вращения всего массива.

Теперь нам нужно повернуть первые k элементов. Поскольку k равно 2, мы повернем элементы на 0 и 1.

Наконец, мы повернем последние элементы от индекса k до конца. Это дает нам окончательный массив, который мы хотим.

Кодирование третьего подхода
Для кодирования этого решения мы напишем функцию с именем reverse внутри функции rotate и вызовем ее три раза. Однако для начала мы внесем те же изменения в k, что и в предыдущих двух подходах.

Затем мы вызовем функцию reverse (которую мы напишем через минуту), и мы вызовем ее три раза. reverse() примет массив, индекс для начала реверсирования и индекс для завершения реверсирования. Итак, первый вызов reverse() передаст nums, 0 (как начальный индекс) и nums.length — 1 (как конечный индекс). Второй вызов reverse() передаст nums, 0 (как начальный индекс) и k — 1 (как конечный индекс). Третий вызов reverse() передаст nums, k (как начальный индекс) и nums.length — 1 (как конечный индекс).

Теперь мы можем написать функцию reverse, параметры которой будут nums, start и end. В этой функции мы переключаем значения в индексе начала и конца и перемещаем начало и конец к центру. Мы продолжаем делать это до тех пор, пока начало меньше конца.

Итак, мы пишем цикл while, который будет продолжаться, пока start меньше end. Внутри цикла мы сохраняем временную переменную, которая хранит значение массива nums в начальном индексе. Затем мы устанавливаем значение в начальном индексе, равное значению в конечном индексе, и значение в конечном индексе, равное временной переменной. Мы перемещаем начало к середине, увеличивая его, и перемещаем конец к середине, уменьшая его. Наконец, когда цикл while будет выполнен, мы вернем nums в функцию rotate.

После выполнения каждой reverse() функции последняя вещь - вернуть nums:

Это решение выполняется в линейном времени (O (n)) и в постоянном пространстве (O (1)).

Дайте мне знать в комментариях, если у вас есть какие-либо вопросы или идеи по другим способам решения этой проблемы!

Ресурсы