我认为，通常情况下，插入到数组的中间(任何位置)可能代价高昂——将元素移动到一个槽上可能需要 O(n) 时间，并且可能需要为数组重新分配内存。另一方面，链接可能需要 O(1) 时间。
但是在 Ruby、Python 和 PHP 中，是否有一个数组对象只需要 O(1) 时间就可以在数组中间插入一个元素？
更新:并且必须遵循的是，在数组中的任何位置替换数组元素或访问它也是 O(1)。
更新:插入如下:
1.9.3-p125 :001 > RUBY_DESCRIPTION
=> "ruby 1.9.3p125 (2012-02-16 revision 34643) [x86_64-darwin11.3.0]"
1.9.3-p125 :002 > a = %w{ a b c d }
=> ["a", "b", "c", "d"]
1.9.3-p125 :007 > a.insert(3, 123)
=> ["a", "b", "c", 123, "d"]
最佳答案
在 PHP 中，您可以使用 \SplDoublyLinkedList 来完成此操作。 http://php.net/manual/en/class.spldoublylinkedlist.php
请注意，PHP 数组不是您在 C、C#、Java 等中看到的数组 - 它们是有序的 HashMap 。参见http://www.php.net/manual/en/language.types.array.php的介绍
根据您的用例(如果这不是家庭作业)，\SplMaxHeap 不是 O(1)，但可能是您的最佳选择。 http://php.net/manual/en/class.splmaxheap.php
关于php - 在 Ruby、Python 或 PHP 中，是否有一个插入到 Array 对象中间需要 O(1) 时间的操作？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10466938/