Обнуление массива за константное время

31 марта 2022, 23:40

На интервью задали такую задачу: дан массив длиной n, необходимо реализовать методы добавления элемента и обнуление(значения всех элементов сбрасывается на 0) массива за константное время. Важное уточнение: использовать тот же массив, без создания нового. Варианты, вроде int[] array = new int[]; не подходят.

Возник вопрос с методом обнуления, не могу понять как реализовать. Есть вот такой способ, с использованием дополнительных массивов: http://efesx.com/2009/11/05/reset-an-array-in-constant-time/ но не могу понять логику решения.

Answer 1

Вставка/удаление

Массив в котором вставка и удаление делаются за константное время это связанный список, то есть список в каждом элементе которого есть ссылка на следующий и/или предыдущий элемент. Обычно реализуется в виде LinkedList

Операция вставки в нем это всего лишь переписывание ссылки на следующий элемент, соответственно это не зависит от размера. Удаление аналогично.

Операция обнуления.

Ну как вариант можно завести булевскую переменную, типа boolean isZero, если он становится true, то любая операция получения значения должна возвращать 0 - надо всего лишь переписать метод получения значения элемента get()