在对数时间内删除TreeMap的子图
我使用 TreeMap 来表示可以包含重复元素的排序列表。键对应于列表中的任意值，映射值对应于出现的次数。我使用排序列表概念是因为我需要有效地操作子列表（log n 时间），并且我使用 TreeMap 因为 Java 没有任何默认的排序列表执行。
但是，我注意到我的算法的性能比预期慢，因此在做了一些研究后，似乎 subMap 方法需要 O(log n< /em> + k) 时间，其中 n 是地图的大小，k 是子地图内的元素数量。对于相对于 n 较大的 k 值，这接近线性时间。
如何在亚线性时间内操作子图（子列表）；或者，是否有更好的方法可以在 Java 中表示排序列表？
这个问题背后的动机：将树图想象成二叉搜索树，我想找到某个子树的第一个节点，然后将其用作整个树本身，有效地删除树的其余部分。理想情况下，这只需要 O(log n) 时间。
I am using a TreeMap<Integer, Integer> to represent a sorted list which can have duplicate elements. The key corresponds to an arbitrary value in the list and the mapped value corresponds to the number of occurrences. I am using a sorted list concept because I need to efficiently operate over sublists (log n time) and I am using a TreeMap because Java doesn't have any default sorted list implementation.
However, I noticed that the performance of my algorithm was slower than expected, so after doing some research, it appears that the subMap method takes O(log n + k) time, where n is the size of the map and k is the number of elements within the sub map. For large values of k relative to n, this approaches linear time.
How can I operate over submaps (sublists) in sublinear time; or alternatively, is there a better way I can represent a sorted list in Java?
The motivation behind this question: imagining the tree map as a binary search tree, I'd like to find the first node of some subtree, then use that as the entire tree itself, effectively removing the rest of the tree. Ideally this would only take O(log n) time.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
Google 的 Guava 库有一个 广泛的集合类套件，很好地补充了标准库中的集合类。
您可能会喜欢他们的
SortedMultiset用于按排序顺序维护元素并允许重复的集合的接口。实现包括：ImmutableSortedMultiset< /代码>TreeMultisetGoogle's Guava library has an extensive suite of collection classes that complement the ones in the standard library nicely.
You might like their
SortedMultisetinterface for collections that maintain elements in a sorted order and allow for duplicates. Implementations include:ImmutableSortedMultisetTreeMultiset