В этой задаче нам предлагается повернуть массив целых чисел на заданное количество шагов. Хотя поиск наиболее оптимизированного решения кажется простым, для большинства из нас он может оказаться захватывающей головоломкой.
В этой статье мы рассмотрим несколько различных подходов к решению этой проблемы. Мы начнем с обсуждения подхода грубой силы, который обеспечивает простое, но наивное решение. Оттуда мы будем двигаться к более оптимизированным методам, которые улучшают как временную, так и пространственную сложность. Но перед этим мы увидим постановку задачи.
Постановка проблемы:
Дан целочисленный массив
nums
, поверните массив вправо наk
шагов, гдеk
неотрицательно.
Следите за обновлениями в следующих разделах, где мы рассмотрим различные подходы к решению этой проблемы.
Подход 1: грубая сила
Подход заключается в выполнении поворота в цикле на заданное количество шагов, сдвигая каждый элемент на одну позицию вправо.
- В этом подходе мы перебираем массив
k
раза. - На каждой итерации мы сдвигаем каждый элемент на одну позицию вправо, заменяя текущий элемент элементом перед ним.
- Последний элемент сохраняется в переменной
lastElement
перед началом процесса сдвига, а затем присваивается первой позицииnums[0]
в конце каждой итерации. - Этот процесс фактически поворачивает массив на
k
шагов вправо.
// ES6 Arrow Function const rotateArray = (nums, k) => { const n = nums.length; k = k % n; for(let i = 0; i < k; i++) { const last = nums[n - 1]; for(let j = n - 1; j > 0; j--) { nums[j] = nums[j-1]; } nums[0] = last; } return nums; }
Временная сложность:O(K * N)
Поскольку мы итерируем массив k
раз, и на каждой итерации он сдвигает каждый элемент на одну позицию вправо. Здесь N
— длина массива.
Пространственная сложность:O(1)
Поскольку он выполняет вращение на месте без использования каких-либо дополнительных структур данных, следовательно, сложность пространства постоянна.
Примечание. Этот подход не считается оптимальным для решения проблемы вращения массива большей длины. Его цель состоит в том, чтобы дать начальную точку зрения на то, как можно подойти к проблеме.
Подход 2. Использование дополнительного пространства
Другой подход предполагает использование дополнительного массива для хранения повернутых элементов. Мы копируем последние k элементов исходного массива в начало нового массива, а затем оставшиеся элементы из исходного массива.
- Поэтому мы создаем новый массив
rotatedArray
для хранения повернутых элементов. - Копируем последние
k
элементов исходного массива в началоrotatedArray
. - Затем мы копируем оставшиеся элементы из исходного массива.
- Верните
rotatedArray
.
// ES6 Arrow Function const rotateArray = (nums, k) => { const n = nums.length; k = k % n; const rotatedArray = []; for(let i = n - k; i < n; i++) { rotatedArray.push(nums[i]); } for(let i = 0; i < n - k; i++) { rotatedArray.push(nums[i]); } return rotatedArray; }
Временная сложность:O(N)
Алгоритм выполняет итерацию по входному массиву один раз, чтобы скопировать элементы в rotatedArray
. Следовательно, временная сложность равна O(n), где N
— размер массива.
Пространственная сложность:O(N)
Здесь создается новый массив для хранения повернутых элементов, и размер этого массива равен размеру входного массива. Таким образом, пространственная сложность равна O(N), так как для этого требуется дополнительное пространство, пропорциональное размеру входных данных.
Подход 3: реверсивный массив
Это оптимизированный подход к решению этой проблемы. Он включает в себя обращение всего массива, за которым следует обращение первых k элементов и оставшихся n-k элементов по отдельности. Такой подход позволяет добиться желаемого поворота на месте без использования дополнительного пространства.
- Мы определяем функцию, которая переворачивает массив, используя индексы
start
иend
, указанные в аргументах. - Во-первых, мы переворачиваем весь входной массив.
- Затем мы обращаем первые
k
элементов в обращенном массиве. - Наконец, мы обращаем оставшиеся
n-k
элементов в обращенном массиве.
// ES6 Arrow Function const reverseArray = (arr, start, end) => { while(start < end) { [arr[start], arr[end]] = [arr[end], arr[start]]; start++; end--; } } const rotateArray = (nums, k) => { const n = nums.length; k = k % n; reverseArray(nums, 0, n-1); reverseArray(nums, 0, k-1); reverseArray(nums, k, n-1); return nums; }
Временная сложность:O(N)
В заданном входном массиве есть три обратные операции над подмассивами. Мы обращаем массив, используя функцию reverseArray
, и временная сложность этой функции составляет O (N). Следовательно, общая временная сложность функции rotateArray
является линейной.
Пространственная сложность:O(1)
Поскольку поворот происходит на месте, не занимая дополнительного места, и мы возвращаем один и тот же массив, сложность пространства постоянна.
Важный:
Почему K = k % n
, где n
– длина входного массива.
Для обработки случаев, когда значение k
больше или равно размеру массива n
. Поскольку поворот массива по его размеру или кратному его размеру приводит к тому же самому массиву, нет необходимости выполнять избыточные повороты. Цель k = k % n
состоит в том, чтобы убедиться, что k
находится в пределах допустимого диапазона поворотов.
Выполняя операцию по модулю (%
) с n
, мы уменьшаем k
до эквивалентного числа оборотов, попадающих в пределы массива. Этот шаг эффективно приводит k
к значению от 0 до n-1
, гарантируя, что оно представляет правильное количество оборотов, необходимое для заданного размера массива.
Например, если массив имеет длину 5 (n = 5), а k
равно 7, операция по модулю k = k % n
установит k
в 2. Это означает, что поворот массива на 7 шагов эквивалентен повороту его на 2 шага в пределах размера массива. . Эта корректировка помогает оптимизировать решение и позволяет избежать ненужных поворотов.
Включение k = k % n
в код гарантирует, что решения работают правильно для любого значения k
, даже если оно превышает размер массива.
И у вас есть это, ребята! Мы исследовали различные подходы, оптимизировали наши решения и, надеюсь, повеселились. Я надеюсь, что эта статья предоставила вам ценную информацию и помогла лучше понять различные подходы к решению этой проблемы. Удачного кодирования!
Проблема: Литкод 189