Задача «Удалить элемент» требует от нас удалить все вхождения заданного значения из массива. Хотя на первый взгляд задача кажется простой, найти наиболее эффективное решение может быть непросто.

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

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

Учитывая массив целых чисел nums и целое число val, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов вnums, которые не равныval.

Рассмотрим количество элементов в nums, которые не равны val быть k, чтобы быть принятыми, вам нужно сделать следующие вещи:

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

Вернуть k.

Итак, давайте погрузимся и изучим различные подходы и их временную и пространственную сложность.

Подход 1. Наивный подход

  1. Переберите массив и проверьте, равен ли каждый элемент целевому значению.
  2. Если элемент равен целевому, удалите его из массива.
  3. Повторяйте этот процесс до тех пор, пока не будут удалены все вхождения целевого значения.
  4. Вернуть длину массива.
// ES6 Arrow Function
const removeElement = (nums, val) => {
    let i = 0; 
    while(i < nums.length) {
        if(nums[i] === val) nums.splice(i, 1);
        else i++;
    }

    return nums.length;
}

Временная сложность: O(N²)

В худшем случае нам, возможно, придется удалить все элементы массива. Поскольку удаление элемента занимает O(N) времени, и мы делаем это для N элементов, где N — длина массива. Это займет O(N²) времени.

Пространственная сложность:O(1)

Поскольку мы изменяем входной массив на месте, для него не требуется дополнительное пространство. Следовательно, постоянная пространственная сложность.

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

  1. Здесь мы используем два указателя, «медленный» и «быстрый», изначально указывающие на начало массива.
  2. Перебрать массив с «быстрым» указателем.
  3. Когда «быстрый» указатель встречает элемент, не равный целевому, скопируйте его в позицию, указанную «медленным» указателем, и увеличьте оба указателя.

Примечание. Тем самым мы эффективно удаляем целевое значение из массива. Этот подход позволяет избежать ненужных операций удаления, что приводит к более высокой производительности, чем наивный подход.

4. Повторяйте этот процесс, пока «быстрый» указатель не достигнет конца массива.

// ES6 Arrow Function
const removeElement = (nums, val) => {
    let slow = 0; 

    for(let fast = 0; fast < nums.length; fast++) {
        if(nums[fast] !== val) {
            nums[slow] = nums[fast];
            slow++;
        }
    }

    return slow;
}

Временная сложность:O(N)

Здесь мы повторяем входной массив один раз, используя быстрый указатель. Таким образом, это дает нам линейную временную сложность.

Пространственная сложность:O(1)

Поскольку мы изменяем массив на месте и не используем дополнительное пространство, сложность пространства постоянна.

Подход 3: оптимизированные два указателя

Таким образом, основная идея состоит в том, чтобы свести к минимуму количество замен элементов.

  1. Мы используем два указателя, «левый» и «правый», изначально указывающие на начало и конец массива соответственно.
  2. Переместите «левый» указатель вправо, пока он не встретит элемент, равный целевому значению.
  3. Переместите «правый» указатель влево, пока он не встретит элемент, отличный от целевого значения.
  4. Если «левый» указатель все еще находится слева от «правого» указателя, поменяйте местами элементы в этих указателях и увеличьте «левый» указатель и уменьшите «правый» указатель.
  5. Повторяйте эти шаги до тех пор, пока «левый» указатель не перестанет находиться слева от «правого» указателя.
// ES6 Arrow Function
const removeElement = (nums, val) => {
    let left = 0; 
    let right = nums.length - 1;

    while(left <= right) {
        if(nums[left] === val) {
            [nums[left], nums[right]] = [nums[right], nums[left]];
            right--;
        } else {
            left++;
        }
    }

    return left;
}

Временная сложность:O(N)

При таком подходе мы уменьшаем количество свопов, но все же итерируемся по массиву один раз. Следовательно, временная сложность линейна.

Пространственная сложность:O(1)

Мы не используем никакого дополнительного пространства, поскольку мы модифицируем входной массив на месте. Таким образом, пространственная сложность постоянна.

И у вас есть это, ребята! Мы исследовали различные подходы, оптимизировали наши решения и, надеюсь, повеселились. Я надеюсь, что эта статья предоставила вам ценную информацию и помогла лучше понять различные подходы к решению этой проблемы. Удачного кодирования!

Задача- Leetcode 27