问题描述
我必须制作具有特定条件的数据结构.
I have to make a data structure with certain conditions.
首先这4个函数必须是O(log(n)):
First these 4 functions must be in O(log(n)):
insert(Object o)
insert(int index, Object o)
delete(int index)
update(int index, Object o)
第二:数据结构必须实现java.util.List
Second: The data structure must implement java.util.List
我的问题是 O(log(n)) 和 List.有很多树可以做O(log(n))中的操作(比如BST、Red-Black Tree、AVL Tree),但是这些树怎么索引,怎么插入到任何地方呢?
My issue is with the O(log(n)) and the List. There are a lot of trees that can do the operation in O(log(n)) (like BST, Red-Black Tree, AVL Tree), but how can these trees be indexed and how can the insert be anywhere?
将其设置为仅列表确实会带来问题.java.util.List
有这些实现类:AbstractList
、AbstractSequentialList
、ArrayList
、LinkedList
、Stack
、Vector
Setting this up as only a list does bring up issues.
java.util.List
has these implementing classes:AbstractList
, AbstractSequentialList
, ArrayList
, LinkedList
, Stack
, Vector
这些类中的大多数都有 O(1) 和 O(1)
Most of these classes have methods of O(1) and O(1) < O(log(n)), but there is always a method that is O(n). Example the ArrayList has a remove of O(n).
有没有人对这个问题有任何建议或方法?
Does anyone have any advise or approaches to this problem?
基本上,我正在寻找一种能够满足这些要求的数据结构.
Basically, I am looking for a data structure that I'll fulfill those requirements.
推荐答案
可索引的跳过列表 似乎符合要求:插入和删除操作是 O(log n),
update
的索引访问也 O(log n).
An indexable skip list seems to fit the bill: inserts and deletes are O(log n), and index access for
update
is also O(log n).
这篇关于列为 O(log(n))的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!