Задача «Удалить элемент» требует от нас удалить все вхождения заданного значения из массива. Хотя на первый взгляд задача кажется простой, найти наиболее эффективное решение может быть непросто.
В этой статье мы рассмотрим три разных подхода к решению этой проблемы, начиная с наивного подхода и постепенно переходя к более оптимизированным решениям.
Постановка проблемы:
Учитывая массив целых чисел
nums
и целое числоval
, удалите все вхожденияval
вnums
на месте. Порядок элементов может быть изменен. Затем верните количество элементов вnums
, которые не равныval
.
Рассмотрим количество элементов в
nums
, которые не равныval
бытьk
, чтобы быть принятыми, вам нужно сделать следующие вещи:
Измените массив
nums
так, чтобы первыеk
элементов массиваnums
содержали элементы, не равныеval
. Остальные элементыnums
не важны, как и размерnums
.
Вернуть
k
.
Итак, давайте погрузимся и изучим различные подходы и их временную и пространственную сложность.
Подход 1. Наивный подход
- Переберите массив и проверьте, равен ли каждый элемент целевому значению.
- Если элемент равен целевому, удалите его из массива.
- Повторяйте этот процесс до тех пор, пока не будут удалены все вхождения целевого значения.
- Вернуть длину массива.
// 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: два указателя
- Здесь мы используем два указателя, «медленный» и «быстрый», изначально указывающие на начало массива.
- Перебрать массив с «быстрым» указателем.
- Когда «быстрый» указатель встречает элемент, не равный целевому, скопируйте его в позицию, указанную «медленным» указателем, и увеличьте оба указателя.
Примечание. Тем самым мы эффективно удаляем целевое значение из массива. Этот подход позволяет избежать ненужных операций удаления, что приводит к более высокой производительности, чем наивный подход.
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: оптимизированные два указателя
Таким образом, основная идея состоит в том, чтобы свести к минимуму количество замен элементов.
- Мы используем два указателя, «левый» и «правый», изначально указывающие на начало и конец массива соответственно.
- Переместите «левый» указатель вправо, пока он не встретит элемент, равный целевому значению.
- Переместите «правый» указатель влево, пока он не встретит элемент, отличный от целевого значения.
- Если «левый» указатель все еще находится слева от «правого» указателя, поменяйте местами элементы в этих указателях и увеличьте «левый» указатель и уменьшите «правый» указатель.
- Повторяйте эти шаги до тех пор, пока «левый» указатель не перестанет находиться слева от «правого» указателя.
// 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