Различные подходы к решению Leetcode 283 в JavaScript
Сегодня мы рассмотрим распространенную проблему, которая часто возникает при работе с целочисленными массивами: как эффективно переместить все 0 в конец, сохранив порядок ненулевых элементов. Хотя поначалу это может показаться простой задачей, эта проблема требует тщательного изучения методов манипулирования массивами и стратегий оптимизации. К концу этой статьи вы будете лучше понимать работу с массивами в целом.
Постановка проблемы:
Учитывая целочисленный массив
nums
, переместите все0
в его конец, сохраняя относительный порядок ненулевых элементов.
Обратите внимание, что вы должны сделать это на месте, не создавая копию массива.
Подход 1: два указателя
- Выполните итерацию по массиву, используя два указателя, один для отслеживания последнего увиденного ненулевого индекса, а другой для итерации по массиву.
- Для каждого обнаруженного ненулевого элемента замените его на элемент с последним ненулевым индексом.
- Этот подход позволяет избежать необходимости в дополнительном массиве.
// ES6 Arrow Function const moveZeroes = nums => { let slowPointer = 0; for(let i = 0; i < nums.length; i++) { if(nums[i] !== 0) { [nums[slowPointer], nums[i]] = [nums[i], nums[slowPointer]]; slowPointer++; } } return nums; }
Временная сложность:O(N)
Пространственная сложность:O(1)
Подход 2: Оптимизированные двухочковые
Подобно подходу с двумя указателями, вместо замены ненулевых элементов последним ненулевым элементом просто замените последний ненулевой элемент текущим ненулевым элементом. Это позволяет избежать ненужных свопов и может повысить производительность.
// ES6 Arrow Function const moveZeroes = nums => { let counter = 0; for(let i = 0; i < nums.length; i++) { if(nums[i] !== 0) { nums[counter] = nums[i]; counter++; } } for(let i = counter; i < nums.length; i++) { nums[i] = 0; } return nums; }
Временная сложность:O(N)
Пространственная сложность:O(1)
Примечание. Этот подход имеет ту же временную сложность O(n), что и предыдущий подход, но на практике он быстрее из-за меньшего количества необходимых операций.
И у вас есть это, ребята! Я надеюсь, что эта статья предоставила вам ценную информацию и помогла лучше понять различные подходы к решению этой проблемы. Удачного кодирования!
Проблема - Leetcode 283