时间戳

首页 > 解决方案 > Java 排序数据结构，允许以对数时间删除某个范围内的值

java - Java 排序数据结构，允许以对数时间删除某个范围内的值

问题描述

我想知道Java内置库中是否有一个接口，它实现了一个有序的数据结构并支持在一定范围内删除。例如，如果我们调用数据结构 S（假设是整数），我希望能够搜索并删除 S 的子集 Q 使得 Q 包含 S 中范围 [start, end ] 在 O(|Q| log |S|) 时间内。

我知道在 C++ 中，Set 接口有一个擦除方法，但 Java 的 TreeSet 似乎没有类似的东西。任何人都可以帮忙吗？谢谢！

标签： javaalgorithmdata-structuresset

解决方案

SortedSet.subSet返回一个视图，然后您可以clear().

例如：

TreeSet<String> set = new TreeSet<>(Arrays.asList("A", "B", "C", "D", "E"));
System.out.println(set);  //  [A, B, C, D, E]
set.subSet("B", "D").clear(); // Inclusive of B, exclusive of D.
System.out.println(set);  //  [A, D, E]

（ 的文档SortedSet描述了如何将 的边界subSet分别修改为独占和包含，至少对于String）。

推荐阅读