英文:
Java sorted data structure that allows for logarithmic time removal of values within a range
问题
我想知道Java内置库中是否有一个实现了有序且支持在范围内进行移除操作的接口。例如，如果我们称这个数据结构为S（假设是整数），我希望能够在O（|Q| log |S|）的时间内搜索并移除S中范围[start, end]内的子集Q，其中Q由S中所有元素组成。
我知道在C++中，Set接口有一个erase方法，但似乎Java的TreeSet没有类似的功能。有人能帮忙吗？谢谢！
英文:
I was wondering if there's an interface in the Java built in libraries that implements a data structure which is ordered and supports removal over a range. For example, if we call the data structure S (let's say of Integers), I'd like to be able to search for and remove the subset Q of S such that Q consists of all elements in S in the range [start, end] in O(|Q| log |S|) time.
I know in C++, there is an erase method to the Set interface, but it doesn't seem like Java's TreeSet has something similar. Can anyone help? Thanks!
答案1
得分: 3
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(); // 从 B（包含）到 D（不包含）的范围。
System.out.println(set); // [A, D, E]
（SortedSet 的文档描述了如何修改 subSet 的界限，至少对于 String，分别为不包含和包含）。
英文:
SortedSet.subSet returns a view, which you can then clear().
For example:
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]
(The documentation of SortedSet describes how to modify the bounds of subSet to be exclusive and inclusive, respectively, at least for String).
答案2
得分: 0
我不知道任何接口/库，但你可以尝试使用类似直方图的结构...
例如，假设我们知道我们的结构只会包含介于 min 和 max 之间（包括边界）的整数。那么我们可以简单地创建一个数组，如下所示...
int[] hist = new int[max - min + 1];
如果我们想要将一个数字 i 添加到直方图中，我们可以简单地执行...
hist[i - min]++;
数组中的每个索引代表预定义范围内的一个数字。数组中的每个值表示范围内一个数字的出现次数。
这个结构非常强大，因为它允许在常数时间内进行添加、删除和搜索。
假设我们想要删除包括范围 Q = [s, e] 内的所有元素。我们可以运行以下线性循环...
for (int i = s; i <= e; i++) {
hist[i - min] = 0;
}
这运行时间为 O(|Q|)。
最后，如果我们想要将上述结构变成一个有序集合而不是有序序列，我们可以将数组更改为持有布尔值而不是整数。
更多信息请参阅 https://en.wikipedia.org/wiki/Counting_sort。
英文:
I don't know of any interfaces/libraries, but you could try using a histogram like structure...
For example, let's say we know our structure will only hold integers between min and max inclusive. Then we can simply make an array in the following manor...
int[] hist = new int[max - min + 1];
If we want to add a number i to the histogram, we can simply do...
hist[i - min]++;
Each index in the array represents a number in the predefined range. Each value in the array represents the number of occurrences of a number in the range.
This structure is extremely powerful since it allows for constant time addition, removal, and search.
Let's say we want to remove all elements in the inclusive range Q = [s, e]. We can run the following linear loop...
for (int i = s; i <= e; i++) {
hist[i - min] = 0;
}
This runs in O(|Q|).
Lastly, If we wanted to make the above structure an ordered set instead of an ordered sequence, we could change our array to hold booleans instead of integers.
For more info check out https://en.wikipedia.org/wiki/Counting_sort.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论