Задача удаления заданных элементов из массива на первый взгляд кажется весьма простой. И на самом деле так оно и есть, однако зачастую начинающие программисты используют более сложный и тяжёлый с точки зрения производительности вариант алгоритма, из-за чего и кода становится больше и эффективность программы страдает. В учебных программах, когда количество элементов массива мало (порядка 10-100 элементов) оба алгоритма выполняются практически мгновенно. Однако при попытке написать наивный вариант в проекте, в котором работают с гигантскими массивами, приложение будет тратить ужасно много времени или вовсе надолго зависнет.
Как удалить одно значение из массива?
Начнём с более простого алгоритма — удаления одного элемента по индексу. Его отлично знают все начинающие разработчики: все элементы правее заданного индекса сдвинуть влево на 1 и уменьшить размер массива на единицу:
// удаление из массива array элемента по индексу index
void RemoveValueAt(int *array, int &n, int index) {
n--; // уменьшаем размер массива
// сдвигаем элементы правее index влево
for (int i = index; i < n; i++) {
array[i] = array[i + 1];
}
}
Этот алгоритм весьма простой и эффективный. К нему никаких претензий.
Наивный алгоритм удаления значений из массива
Когда же нужно удалить не один элемент из массива, а сразу несколько, в первую очередь в голову приходит мысль вызвать удаление по индексу несколько раз. Выглядеть это будет примерно следующим образом:
// удаление из массива array элементов равных value
void RemoveValues(int *array, int &n, int value) {
for (int i = n - 1; i >= 0; i--) {
if (array[i] == value) { // если нужно удалить элемент
RemoveAt(array, n, i); // удаляем его по текущему индексу
}
}
}
В такой версии может показаться, что всё хорошо и алгоритм имеет линейную сложность. Но давайте заменим вызов функции RemoveAt на её тело:
// удаление из массива array элементов равных value
void RemoveValues(int *array, int &n, int value) {
for (int i = n - 1; i >= 0; i--) {
if (array[i] == value) { // если нужно удалить элемент
n--; // уменьшаем размер массива
// сдвигаем элементы правее i влево
for (int j = i; j < n; j++) {
array[j] = array[j + 1];
}
}
}
}
В таком виде всё куда очевиднее: при каждом удалении элемента выполняется вложенный цикл, из-за чего сложность удаления элеметнов равных заданному значению становится квадратичной. Можно ли как-то избавиться от вложенного цикла? Оказывается, можно, и, что самое главное, просто необходимо!
