如何设计一个 arraylike 数据结构，支持 O(1) 的按索引访问和 O(1) 的按索引删除.

[littleMaple]

用代码来作为例子，假设我们的数据结构名为 MagicArray：

magic_array = MagicArray("How are you", "I am find", "Thank you", "And you")

print(magic_array[2])  # 这一行应该打印 "Thank you"，且该行的运行时间应该与 magic_array 的长度无关，或者至少“摊还地”无关.

magic_array.remove(1)  # 这一行的运行时间应该与 magic_array 的长度无关，或者至少“摊还地”无关.

print(magic_array[2])  # 这一行应该打印 "And you"，且该行的运行时间应该与 magic_array 的长度无关，或者至少“摊还地”无关.

如果我们无法设计出这样的数据结构，我们如何形式证明它不可能存在？如果确实不可能存在，我们可以设计出的最接近它的最快的数据结构能够有多快？

[xupefei]

链表+位置到节点的哈希表。
这题算是 leetcode 中等难度。

[php8]

咱 php 数组插入和删除都是 O(1)滴，还能当 map 用，难怪被公认是最好的语言

[xupefei]

@xupefei 不过我这个办法删除比 O1 复杂，最坏情况下是 On 。
用 jumplist 可能会更好

[littleMaple]

@xupefei #1 删除操作的时候维护「位置映射到节点的哈希表」就需要 O(n) 的复杂度吧？例如 magic_array.remove(1) 操作运行的时候，2->"Thank you" 和 3->"And you" 这两个映射就需要更新成 1->"Thank you" 和 2->"And you"。

[xupefei]

最好的办法应该是用 rope，能做到 logn 复杂度

[sunkai0609]

php 的数组

[sunkai0609]

@sunkai0609 请无视我

[hanxiV2EX]

跳跃表，redis 的 zset

只能做到 lgn

[love]

这和 map 用整数做 key 有什么区别?

[mxT52CRuqR6o5]

@php8 我 google 了一下 php 的 array_splice 可并不是 O(1)而是 O(offset+length)啊

[mxT52CRuqR6o5]

这个问题一两句应该证明不了，书上也许会有答案

[raaaaaar]

结合链表的增删和数组的查改优点就是跳表，所以不可能存在你说得这种上界都是 O(1) 的。
查找操作最好的就是利用内存的随机存取特点，但是要实现删除操作就必然和随机存取冲突，因为删除节点内存就变了，地址也变了，要不影响随机存取，内存肯定要移动的。

[littleMaple]

@love #9 因为要求是 arraylike，例如如果删除了第三个元素，第四个元素至最后一个元素对应的索引都要相应的减一.

[littleMaple]

@raaaaaar #12 确实如此，直观上来说 O(1) access 和 O(1) remove 不可能同时满足，但是若是 amortized O(1) access 和 amortized O(1) remove 呢？放宽一点要求之后不知道能不能同时满足.

[php8]

@mxT52CRuqR6o5 是我理解有误，没有考虑到删除之后下标要依次挪一格

[wangxiyu191]

没要求插入的时间和空间复杂度，钻个空子。可以在初始化 /插入时就生成好一次或多次删除后可能达到的所有的状态。这样插入和删除就都能做 O(1) 了。

[wangxiyu191]

@wangxiyu191 上面最后一句打错。“这样插入和删除就都能做 O(1) 了” -》 “这样查询和删除就都能做 O(1) 了”

[sunnybird]

算法核心思想，空间换时间

[shiji]

@littleMaple Hashmap 的核心不就是 array 么。 又没有必要说 array 不能留空，必须一字排开

[littleMaple]

@wangxiyu191 #16 你居然能想到这样暴力的方案 XD 而且居然是对的.