表示具有3个操作的双值数组的数据结构

Question

让我们有n价值观.所有值都false可以更改为true.我想对这些值进行3次操作,并且具有一定的时间复杂度:

• val(i)- >返回索引处的值i.时间复杂度 - O(1).
• change(i)- >将index的值更改i为true.时间复杂度 - 摊销O(1).
• find(i)- >最接近的索引返回到索引i,包含值 false(如果有false上i然后返回i).时间复杂度 - O(log n).

我并不关心空间复杂性.结构在开始时以固定长度初始化.初始化需要多长时间并不重要.

用于这些操作的数据结构应该如何？

Answer 1

使用哈希图和二叉搜索树的组合。

示例 - 假设 boolean[] A = { false, false, false, false}

创建 hashmap（映射的键为整数，值为对象）

迭代每个项目： 1. 创建以索引和值作为属性的对象。2. 将对象添加到地图。3. 使用 BST 中位置的对象索引将相同的对象添加到 BST。

现在进行如下操作：

1. Val(i) ：直接获取对象并返回对象的值。复杂性 (1)

2. Change(i, true/false) ：再次从映射中获取对象并更新其值。复杂度 O(1)

3. Find(i) ：检查该映射中对象的值是否为假。如果为 false，则返回，否则在 BST 中遍历以检查值为 false 的最近索引。注意，基于对象的键来遍历 BST 可以在 O(logn) 内完成。因此复杂度为 O(logn)