数据结构 - O(1) 复杂度
Data structures - O(1) complexity
所以我得到了下一个问题：
通过以下接口描述一个数据结构：
- 该结构将包含 n 个元素，其中每个元素包含一个键和一个值（意思是，每个元素都是（键，值））。
- insert((key, value))：在O(1)平均情况和O(log n)最坏情况下插入一个元素。
- delete((key, value)): 在O(1) 平均情况和O(log n) 最坏情况下删除给定键对应的元素。
- find(key): 找到对应于给定键的元素，return它在 O(1) 平均情况和 O(log n) 最坏情况下的值。
- setAll(m): 将结构体中每个元素的值改成m O(1) worst case
所以我的主要想法是使用哈希 table 来确保插入、删除、查找的平均情况运行时间为 O(1)。哈希 table 将通过链接实现，但使用 AVL 树而不是链表，因此在最坏的情况下，插入、删除和查找将是 O(log n)。
但是我卡在了 setAll 上。我无法在 O(1) 最坏情况下运行时处理这个问题。我知道你不能真正改变所有的值，因为它需要遍历元素，所以我想也许我可以使用全局变量并跟踪对 setAll 的调用，但我真的看不出我是如何实现这样的事情的。
此外，space 复杂度没有限制，这就是我使用包含 AVL 树的散列 table 的原因。这也是我们讲师给我们的线索
使用 AVL 树的散列 table 是一个好的开始。
为了实施setAll(m)，保留一个操作计数器，并在insert期间用update_op = operation_count标记每个条目。
调用setAll(m)时，设置字段last_reset = operation_count和reset_value = m。
然后修改 find 以便它 returns reset_value 对于任何带有 update_op < last_reset 的条目。
所以我得到了下一个问题： 通过以下接口描述一个数据结构：
- 该结构将包含 n 个元素，其中每个元素包含一个键和一个值（意思是，每个元素都是（键，值））。
- insert((key, value))：在O(1)平均情况和O(log n)最坏情况下插入一个元素。
- delete((key, value)): 在O(1) 平均情况和O(log n) 最坏情况下删除给定键对应的元素。
- find(key): 找到对应于给定键的元素，return它在 O(1) 平均情况和 O(log n) 最坏情况下的值。
- setAll(m): 将结构体中每个元素的值改成m O(1) worst case
所以我的主要想法是使用哈希 table 来确保插入、删除、查找的平均情况运行时间为 O(1)。哈希 table 将通过链接实现，但使用 AVL 树而不是链表，因此在最坏的情况下，插入、删除和查找将是 O(log n)。 但是我卡在了 setAll 上。我无法在 O(1) 最坏情况下运行时处理这个问题。我知道你不能真正改变所有的值，因为它需要遍历元素，所以我想也许我可以使用全局变量并跟踪对 setAll 的调用，但我真的看不出我是如何实现这样的事情的。 此外，space 复杂度没有限制，这就是我使用包含 AVL 树的散列 table 的原因。这也是我们讲师给我们的线索
使用 AVL 树的散列 table 是一个好的开始。
为了实施setAll(m)，保留一个操作计数器，并在insert期间用update_op = operation_count标记每个条目。
调用setAll(m)时，设置字段last_reset = operation_count和reset_value = m。
然后修改 find 以便它 returns reset_value 对于任何带有 update_op < last_reset 的条目。