O（1）随机访问和删除的有序列表 [英] Ordered list with O(1) random access and removal

问题描述

是否存在具有以下属性的数据结构：

• 元素以某种顺序存储


• 在给定索引下访问元素需要O（1）时间（可能摊销）


• 删除元素需要分摊O（1）时间，并适当地更改索引（因此，元素0被删除，对元素0的下一次访问应返回旧元素1）

对于上下文，我从编程竞赛：

在 m 个查询中，返回 k 还没有返回的最小的正数。您可以假定返回的数字小于某个常量 n 。

如果上述数据结构存在，则您可以通过创建数字1到 n 的列表在 O（m）时间内完成此操作。然后，对于每个查询，在索引 k 中找到元素并将其删除。在比赛本身中，我的解决方案最终是在某些输入上为 O（m ^ 2）。

I'我很确定您可以使用二进制搜索树在 O（m log m）中执行此操作，但是我想知道是否理想的 O（m） 可以访问。我在网上发现的东西往往很接近，但还不是很远-棘手的是，您可以从列表中的任何位置删除元素。

解决方案方案

1. 使用可以除去 O（1）链表

   
   
   

   每个元素都有指向下一个和上一个元素的指针，因此删除操作只会删除该元素并设置其邻居的指针，例如：

     element [ix-1] .next = element [ix + 1] .prev 
     




2. 访问 O（1）中索引处的有序元素可以使用索引数组

   完成，因此您拥有像这样的无序数组dat [] 和像 idx [] 这样的索引数组对元素 ix 的访问只是：

     dat [idx [ix]] 
     




3. 现在的问题是立即拥有这些属性

   
   
   

   您可以y具有带有索引数组的链表，但删除操作需要更新索引表，在最坏的情况下，该索引表为 O（N）。

   
   
   

   如果您只有索引数组，则删除也是 O（N）

   
   
   

   具有树形结构形式的索引，则删除可能接近 O（log（N）），但访问量也将约为 O（log（N））

Does there exist a data structure with the following properties:

• Elements are stored in some order
• Accessing the element at a given index takes O(1) time (possibly amortized)
• Removing an element takes amortized O(1) time, and changes the indices appropriately (so if element 0 is removed, the next access to element 0 should return the old element 1)

For context, I reduced an algorithm question from a programming competition to:

Over m queries, return the kth smallest positive number that hasn't been returned yet. You can assume the returned number is less than some constant n.

If the data structure above exists, then you can do this in O(m) time, by creating a list of numbers 1 to n. Then, for each query, find the element at index k and remove it. During the contest itself, my solution ended up being O(m^2) on certain inputs.

I'm pretty sure you can do this in O(m log m) with binary search trees, but I'm wondering if the ideal O(m) is reachable. Stuff I've found online tends to be close, but not quite there - the tricky part is that the elements you remove can be from anywhere in the list.

解决方案

1. well the O(1) removal is possible with linked list

   each element has pointer to next and previous element so removal just deletes element and sets the pointers of its neighbors like:

   element[ix-1].next=element[ix+1].prev
   

2. accessing ordered elements at index in O(1) can be done with indexed arrays

   so you have unordered array like dat[] and index array like idx[] the access of element ix is just:

   dat[idx[ix]]
   

3. Now the problem is to have these properties at once

   you can try to have linked list with index array but the removal needs to update index table which is O(N) in the worst case.

   if you have just index array then the removal is also O(N)

   if you have the index in some form of a tree structure then the removal can be close to O(log(N)) but the access will be also about O(log(N))

这篇关于O（1）随机访问和删除的有序列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！