javascript - 在第一个位置插入一维数组中的元素

Question

我在一次 Javascript 面试中被问到这个问题，遗憾的是，我想不出比当时显而易见的答案更好的答案:创建一个新数组，为第一个位置分配新值并复制其余部分。

就时间和空间复杂度而言，在第一个位置插入一维数组中的元素的最佳算法是什么？

编辑:没有像 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。

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

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