Различные подходы к решению Leetcode 283 в JavaScript

Сегодня мы рассмотрим распространенную проблему, которая часто возникает при работе с целочисленными массивами: как эффективно переместить все 0 в конец, сохранив порядок ненулевых элементов. Хотя поначалу это может показаться простой задачей, эта проблема требует тщательного изучения методов манипулирования массивами и стратегий оптимизации. К концу этой статьи вы будете лучше понимать работу с массивами в целом.

Постановка проблемы:

Учитывая целочисленный массив nums, переместите все 0 в его конец, сохраняя относительный порядок ненулевых элементов.

Обратите внимание, что вы должны сделать это на месте, не создавая копию массива.

Подход 1: два указателя

  1. Выполните итерацию по массиву, используя два указателя, один для отслеживания последнего увиденного ненулевого индекса, а другой для итерации по массиву.
  2. Для каждого обнаруженного ненулевого элемента замените его на элемент с последним ненулевым индексом.
  3. Этот подход позволяет избежать необходимости в дополнительном массиве.
// 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