1

我认为通常情况下，插入到数组的中间（任何位置）可能会很昂贵——将元素移动到一个插槽上可能需要 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"]
4

3 回答 3

2

在 PHP 中，您\SplDoublyLinkedList可以为您做到这一点。http://php.net/manual/en/class.spldoublylinkedlist.php

请注意，PHP 数组不是您在 C、C#、Java 等中看到的数组 - 它们是有序的哈希映射。请参阅http://www.php.net/manual/en/language.types.array.php的介绍

根据您的用例（如果这不是家庭作业），\SplMaxHeap不是 O(1)，但可能是您的最佳选择。http://php.net/manual/en/class.splmaxheap.php

于 2012-05-05T23:59:47.510 回答
0

在 Ruby 中使用内置方法是不可能做到这一点的。

于 2012-05-06T02:59:51.707 回答
0

鉴于讨论，在 Python 中可能collections.deque适合您的描述。它是一个双端队列，似乎被实现为双向链表。

于 2012-05-06T00:26:01.320 回答