arrays - 在数组中的特定索引处插入元素

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 移动到结束)但我不太确定这个假设在多大程度上是正确的 - 考虑到移动一个元素需要两个涉及内存的汇编操作(从内存地址到寄存器并返回到新的内存地址)与一个涉及内存的操作(从内存地址到寄存器)和一个用于比较的算术运算

最坏的情况是没有相等的元素彼此相邻 - 在这种情况下，我们将在每次迭代中同时进行比较和移位。