如何设计一个 arraylike 数据结构，支持 O(1) 的按索引访问和 O(1) 的按索引删除.
littleMaple · 2021-01-07 21:25:05 +08:00 · 2127 次点击这是一个创建于 1414 天前的主题，其中的信息可能已经有所发展或是发生改变。
用代码来作为例子，假设我们的数据结构名为 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