随机存取链表的数据结构
我需要一个数据结构，将能够为给定的int提供前面和后面的邻居，这是结构的一部分。
-
null
- LinkedHashSet:查找项目非常快，顺序为O(1)，检索下一个邻居非常快。没有明显的方法可以在不对集合进行反向排序的情况下获得上一个邻居。仅限装箱整数对象。
- int[]:非常容易存储，因为不需要装箱，获取上一个和下一个邻居非常快，但由于索引未知，需要数组遍历，所以对项的检索是O(n)，这是不可接受的。
我现在使用的是int[]和HashMap的组合：
- hashmap，用于在int[] 中检索特定int的索引
- int[]，用于检索该int 的邻居
-
null
- HashMap进行两次装箱（键和值）
- ints存储两次（在映射和数组中）
- 理论上的内存使用可以大大提高
我很想知道更好的解决办法。
共有1个答案
一个解决方案是在添加元素时对数组进行排序。这样，前一个元素总是i-1，要找到一个值，可以使用二进制搜索，即O（log(N))。
下一个明显的候选者是平衡二叉树。对于这种结构，insert有点昂贵，但查找也是O（log(N))。
如果这些值不是32bit，那么您可以使用第二个数组来加快查找速度，其中每个值都是第一个数组中的索引，而该索引就是您要查找的值。
相关的：
- http://java-performance.info/implementing-world-fesport-java-int-int-hash-map/
- HashMap和int作为键
-
我有两个集合A和B的元素a和b。现在它们彼此相关（0...1： n基数），所以每个a在B中最多有一个伙伴，每个b可以与A中的项目有几个（至少一个）关联。A是一组整数对，B是整数。 有没有有效的方法来存储这种“双向”地图？一种简单的方法是使用两种地图： 但也许有更好的方法来更有效地处理这个问题。 谢谢你的帮助
-
我目前正在研究普林斯顿算法第一部分的队列分配。其中一个任务是实现随机队列。这是一个关于使用不同数据结构的实现和权衡的问题。 问题: 随机化队列类似于堆栈或队列，只是从数据结构中的项中均匀随机地选择删除的项。创建实现以下API的通用数据类型： 这里的问题是实现de队列操作和迭代器，因为de队列删除并返回随机元素，迭代器以随机顺序迭代队列。 1.数组实现： 我考虑的主要实现是数组实现。除了随机性之外，
-
本文向大家介绍随机链表的复制相关面试题，主要包含被问及随机链表的复制时的应答技巧和注意事项，需要的朋友参考一下 考察点：链表
-
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Document</title> </head> <body> <script> function Node(element){ this.element=element; this.next=null; } function Point(x,
-
洗牌算法 洗牌算法，顾名思义，就是只利用一次循环等概率的取到不同的元素(牌)。 如果元素存在于数组中，即可将每次 random 到的元素 与 最后一个元素进行交换，然后 count—，即可。 这相当于把这个元素删除，代码如下： #include <iostream> #include <ctime> using namespace std; const int maxn = 10; int a[m
-
本文向大家介绍浅谈PHP链表数据结构(单链表)，包括了浅谈PHP链表数据结构(单链表)的使用技巧和注意事项，需要的朋友参考一下 链表：是一个有序的列表，但是它在内存中是分散存储的，使用链表可以解决类似约瑟夫问题，排序问题，搜索问题，广义表 单向链表，双向链表，环形链表 PHP的底层是C，当一个程序运行时，内存分成五个区（堆区，栈区，全局区，常量区，代码区） 规定：基本数据类型，一般放在栈区 复合数