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

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 而且居然是对的.

• 主 資深大佬 : littleMaple

  @shiji #19 我说的 arraylike 不是这个意思，你可以看我写在标题里的那一段代码，这个数据结构应该要能够满足那里描述的行为.

• 資深大佬 : ericls

  那就让插入贵一点嘛