在第一个位置插入1D数组中的元素

Question

我在一次Javascript采访中被问到这个问题,遗憾的是,我当时无法得到比当时显而易见的答案更好的答案:创建一个新阵列,为第一个位置分配新值并复制其余位置.

在第一个位置插入1D数组中的元素时,在时间和空间复杂度方面最好的算法是什么？

编辑:没有内置功能,如unshift(),splice(),push()而且都可以使用.

Answer 1

如果任务是简单地在普通一维数组的头部插入一个元素，那么我认为您唯一的选择就是这种 O(N) 方法：

for(var i = ary.length; i > 0; i--) {
    ary[i] = ary[i - 1];
}
ary[0] = value;

如果目标是优化在数组开头插入元素的操作（例如，需要经常执行该操作），您可以做的是创建一个数据结构，在数组开头维护一个具有空白空间的数组。开始和结束，以及第一个和最后一个填充项的位置：

_ _ b d f a _ _ 
0 1 2 3 4 5 6 7

这允许您在 O(1) 摊销时间内在数据结构的开头和结尾插入和删除项目，只需更新开头或结尾的索引并将值插入下一个空位置，尽管最坏的情况空间使用量为2N。

当数组的开头或结尾填满时，创建一个新数组，其大小是前一个数组的两倍，并将旧数组的值复制到新数组的中间。

我不知道这是否符合你面试问题的限制，但很多面试问题更多的是测试你思考问题的能力，以及你对算法的了解，而不是给出一个正确的答案。