如何设计一个 arraylike 数据结构，支持 O(1) 的按索引访问和 O(1) 的按索引删除.
littleMaple 2021-01-07 21:25:05 +08:00 2489 次点击这是一个创建于 1740 天前的主题，其中的信息可能已经有所发展或是发生改变。
用代码来作为例子，假设我们的数据结构名为 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 的长度无关，或者至少“摊还地”无关. 如果我们无法设计出这样的数据结构，我们如何形式证明它不可能存在？如果确实不可能存在，我们可以设计出的最接近它的最快的数据结构能够有多快？
22 条回复 2021-01-08 03:17:53 +08:00
 | 1 xupefei 2021-01-07 21:28:06 +08:00 via iPhone 链表+位置到节点的哈希表。 这题算是 leetcode 中等难度。 |
 | 2 php8 2021-01-07 21:28:42 +08:00 via Android 咱 php 数组插入和删除都是 O(1)滴，还能当 map 用，难怪被公认是最好的语言 |
| 3 xupefei 2021-01-07 21:33:10 +08:00 via iPhone @xupefei 不过我这个办法删除比 O1 复杂，最坏情况下是 On 。 用 jumplist 可能会更好 |
 | 4 littleMaple OP @xupefei #1 删除操作的时候维护「位置映射到节点的哈希表」就需要 O(n) 的复杂度吧？例如 magic_array.remove(1) 操作运行的时候，2->"Thank you" 和 3->"And you" 这两个映射就需要更新成 1->"Thank you" 和 2->"And you"。 |
| 5 xupefei 2021-01-07 21:36:17 +08:00 via iPhone  1 最好的办法应该是用 rope，能做到 logn 复杂度 |
 | 6 sunkai0609 2021-01-07 22:06:26 +08:00 php 的数组 |
| 7 sunkai0609 2021-01-07 22:07:54 +08:00 @sunkai0609 请无视我 |
 | 8 hanxiV2EX 2021-01-07 22:10:50 +08:00 via Android 1 跳跃表，redis 的 zset 只能做到 lgn |
 | 9 love 2021-01-07 23:18:15 +08:00 via Android 这和 map 用整数做 key 有什么区别? |
 | 10 mxT52CRuqR6o5 2021-01-07 23:41:16 +08:00 via Android @php8 我 google 了一下 php 的 array_splice 可并不是 O(1)而是 O(offset+length)啊 |
| 11 mxT52CRuqR6o5 2021-01-07 23:42:31 +08:00 via Android 1 这个问题一两句应该证明不了，书上也许会有答案 |
 | 12 raaaaaar 2021-01-07 23:55:06 +08:00 via Android 1 结合链表的增删和数组的查改优点就是跳表，所以不可能存在你说得这种上界都是 O(1) 的。 查找操作最好的就是利用内存的随机存取特点，但是要实现删除操作就必然和随机存取冲突，因为删除节点内存就变了，地址也变了，要不影响随机存取，内存肯定要移动的。 |
| 13 littleMaple OP @love #9 因为要求是 arraylike，例如如果删除了第三个元素，第四个元素至最后一个元素对应的索引都要相应的减一. |
| 14 littleMaple OP @raaaaaar #12 确实如此，直观上来说 O(1) access 和 O(1) remove 不可能同时满足，但是若是 amortized O(1) access 和 amortized O(1) remove 呢？放宽一点要求之后不知道能不能同时满足. |
| 15 php8 2021-01-08 00:50:39 +08:00 via Android @mxT52CRuqR6o5 是我理解有误，没有考虑到删除之后下标要依次挪一格 |
 | 16 wangxiyu191 2021-01-08 01:51:39 +08:00 2 没要求插入的时间和空间复杂度，钻个空子。可以在初始化 /插入时就生成好一次或多次删除后可能达到的所有的状态。这样插入和删除就都能做 O(1) 了。 |
| 17 wangxiyu191 2021-01-08 01:53:12 +08:00 @wangxiyu191 上面最后一句打错。“这样插入和删除就都能做 O(1) 了” -》 “这样查询和删除就都能做 O(1) 了” |
 | 18 sunnybird 2021-01-08 02:14:16 +08:00 via Android 算法核心思想，空间换时间 |
 | 19 shiji 2021-01-08 02:42:37 +08:00 via iPhone @littleMaple Hashmap 的核心不就是 array 么。 又没有必要说 array 不能留空，必须一字排开 |
| 20 littleMaple OP @wangxiyu191 #16 你居然能想到这样暴力的方案 XD 而且居然是对的. |
| 21 littleMaple OP @shiji #19 我说的 arraylike 不是这个意思，你可以看我写在标题里的那一段代码，这个数据结构应该要能够满足那里描述的行为. |
 | 22 ericls 2021-01-08 03:17:53 +08:00 via iPhone 那就让插入贵一点嘛 |
Select Language