寻找一种数据结构,逻辑上表示由唯一标识符(为了简单起见,我们将其视为字符串或至少是可哈希对象) 键入的元素序列。每个元素只能出现一次,没有间隙,第一个位置为0。
应支持以下操作(用单字母字符串演示):
- `insert(id, position)` - 在偏移量`position`处将键入`id`的元素添加到序列中。自然情况下,序列中稍后的每个元素的位置都会增加1。例如: `[S E L F].insert(H,1) -> [S H E L F]` - `remove(position)` - 移除偏移量`position`处的元素。将序列中稍后的每个元素的位置减1。例如: `[S H E L F].remove(2) -> [S H L F]` - `lookup(id)` - 查找由`id`键入的元素的位置。`[S H L F].lookup(H) -> 1`
朴素实现可以是链表或数组。两者都将提供O(n)`lookup`,`remove`和`insert`。
在实践中,`lookup`可能被使用得最多,而`insert`和`remove`足够频繁,以致于不要线性(哈希图+数组/列表的简单组合会让你获得这些功能)。
在完美的世界中,它将是O(1)`lookup`,O(log n)`insert` / `remove`,但我实际上怀疑这不会从纯信息论的角度起作用(尽管我还没有尝试),因此O(log n)`lookup`仍然很好。
应支持以下操作(用单字母字符串演示):
- `insert(id, position)` - 在偏移量`position`处将键入`id`的元素添加到序列中。自然情况下,序列中稍后的每个元素的位置都会增加1。例如: `[S E L F].insert(H,1) -> [S H E L F]` - `remove(position)` - 移除偏移量`position`处的元素。将序列中稍后的每个元素的位置减1。例如: `[S H E L F].remove(2) -> [S H L F]` - `lookup(id)` - 查找由`id`键入的元素的位置。`[S H L F].lookup(H) -> 1`
朴素实现可以是链表或数组。两者都将提供O(n)`lookup`,`remove`和`insert`。
在实践中,`lookup`可能被使用得最多,而`insert`和`remove`足够频繁,以致于不要线性(哈希图+数组/列表的简单组合会让你获得这些功能)。
在完美的世界中,它将是O(1)`lookup`,O(log n)`insert` / `remove`,但我实际上怀疑这不会从纯信息论的角度起作用(尽管我还没有尝试),因此O(log n)`lookup`仍然很好。