вставить элемент в массив по указанному индексу

Question

Меня попросили в интервью вставить элемент в индекс (индекс был дан) наиболее оптимизированным способом.

Я уже пробовал это

  /* Make room for new array element by shifting to right */
            for(i=size; i>=pos; i--)
            {
                arr[i] = arr[i-1];
            }
             arr[pos-1] = num; /* Insert new element at given position and increment size */ 
             size++;

Есть лиЕсть ли лучший способ, чем это сделать?

Answer 1

вы можете выполнить следующую оптимизацию:

-ввести итератор на позицию последнего элемента и выполнять итерацию справа налево, пока не достигнете pos и, очевидно, поддерживая переменную last, которая хранит последний новый встреченный элемент
-на каждой итерации проверять, равен ли текущий элемент last, если да, пропустить его, если нет, скопировать текущий элемент в current_index+1 и присвоить текущий элемент переменной last
-конечно назначить новыйэлемент к pos

Как мы видим, этот подход основан на предположении, что сравнение дешевле, чем сдвиг (т.е. лучше проводить сравнение на каждой итерации и сдвигать элемент время от времени, а не сдвигать ВСЕэлементы от pos до конца), но я не совсем уверен, в какой степени это предположение верно - учитывая, что перемещение элемента потребует двух операций сборки с использованием памяти (из адреса памяти для регистрации и обратно в новый адрес памяти).против одной операции с участием памяти (из памяти в регистр) и однойарифметическая операция для сравнения

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