时间戳

首页 > 解决方案 > 通过索引和元素删除快速查找的数据结构

algorithm - 通过索引和元素删除快速查找的数据结构

问题描述

摘要：我有一段代码想要初始化一个数组，然后迭代地查找一个索引，获取值，然后删除该索引处的元素，将上面的所有值向下移动一个索引。使用普通数组执行此操作是 θ(n^2)。如果有比我想出的更好的方法，我想。

抽象数据类型需要支持： 用一开始就知道的所有数据进行初始化。查找索引的值。删除索引，通过将所有元素向左移动来填补空白。

我想出的数据结构：一棵完整的二叉树，在叶子和内部节点处具有“索引”，存储被填充的叶子数量。初始化非常简单，并且是 nlogn 索引是通过从根检查其子节点的计数并递归到正确的子节点来完成的。一旦你在一个叶子删除是通过清空数据然后回到树上，将所有计数减 1 logn。

使用 nlogn 初始化和 n 个已登录的索引/删除，整个运行时间为 nlogn。

标签： algorithmdata-structuresabstract-data-typearray-splice

解决方案

我在想也许我们可以使用带有双链表的哈希图

在初始化时，用给定的数组值作为键填充哈希图，并使用指向链表节点的指针（迭代器）作为哈希图的值，也填充双链表

尝试删除时，使用hashmap根据值找到指针，并删除链表中的节点

这样，初始化是 O(n)，操作是 O(1)

推荐阅读