Вставка неизвестного количества элементов в динамический массив за линейное время

Question

(Этот вопрос вдохновлен deque :: insert () по индексу? , я был удивлен, что он не был рассмотрен в моей лекции по алгоритму, и что я также не нашел его упомянутым в другой вопрос здесь и даже не в википедии :). Я думаю, что это может представлять общий интерес, и я сам отвечу на него ...)

Динамические массивы - это структуры данных, которые позволяют добавлять элементы в конце в амортизированном постоянном времени O(1) (удваивая размер выделенной памяти при каждом увеличении, см. Амортизированное время динамического массива для краткого анализа).

Однако для вставки одного элемента в середину массива требуется линейное время O(n), поскольку в худшем случае (т.е. вставка в первую позицию) все остальные элементы должны быть сдвинуты на единицу.

Если я хочу вставить элементы k по определенному индексу в массиве, наивный подход к выполнению операции вставки k раз приведет к сложности O(n*k) и, если k=O(n), к квадратичная сложность O(n²).

Если я заранее знаю k, решение довольно простое: при необходимости разверните массив (возможно, перераспределяя пространство), сдвиньте элементы, начиная с точки вставки, на k и просто скопируйте новые элементы.

Но могут быть ситуации, когда я не знаю количество элементов, которые я хочу вставить заранее: например, я могу получить элементы из потокового интерфейса, поэтому я получаю флаг только тогда, когда последний элемент читать.

Есть ли способ вставить несколько (k) элементов, где k заранее неизвестен, в динамический массив в последовательных позициях в линейном времени?

Answer 1

Вы можете просто выделить новый массив длиной k + n и вставить нужные элементы линейно.

newArr = new T[k + n];

for (int i = 0; i < k + n; i++)
    newArr[i] = i <= insertionIndex      ? oldArr[i]
              : i <= insertionIndex + k  ? toInsert[i - insertionIndex - 1]
              :                            oldArr[i - k];

return newArr;

Каждая итерация занимает постоянное время и выполняется k+ n раз, таким образом O (k + n) (или, O (n) , если хотите).

Answer 2

На самом деле есть способ, и он довольно прост:

• Сначала добавьте все k элементы в конце массива. Поскольку добавление одного элемента занимает O(1) времени, это будет сделано за O(k) времени.
• Второй Поворот элементов на место. Если вы хотите вставить элементы в положение index. Для этого вам нужно повернуть подмассив A[pos..n-1] на k позиций вправо (или n-pos-k позиций влево, что эквивалентно). Поворот может быть выполнен за линейное время с использованием обратной операции, как описано в Алгоритм вращения массива за линейное время . Таким образом, время, необходимое для вращения, составляет O(n).

Следовательно, общее время для алгоритма составляет O(k)+O(n)=O(n+k). Если количество вставляемых элементов порядка n (k=O(n)), вы получите O(n+n)=O(2n)=O(n) и, следовательно, линейное время.