假设我们有一个相互排斥的集合。
A = {1,2,3}, B = {4,5,6}, C = {7,8,9},D = {10,11,12}
并且给定一个值Z,例如3,我希望它返回集合A的索引,因为A有3作为它的成员。
问题是,如何使用C++或JAVA.有效地完成这一任务?
My当前解决方案:将A、B、C、D存储为容器中的HashSet (或C++中的unordered_set ),并循环遍历每个集合,直到找到包含Z的集合为止。
另一个问题是,对于存储在容器中的集合的数量,复杂度是O(n)。
有比O(N)更快的方式(或任何数据结构来存储这些集)吗?
发布于 2014-06-07 07:47:04
您可以创建一个映射来映射一个值来设置id(例如,它应该将1、2、3映射到A、4、5和6映射到B等等)。有了散列映射,它平均可以在O(1)中工作。
发布于 2014-06-07 12:47:56
作为一个快速的启发,可以帮助尝试泡泡,最积极地使用在列表中的设置。很可能大多数情况下会有一到两组在80%-90%的请求中返回。
int getSetIndex(Object elem) {
Set first = sets.get(0);
if (first.contains(elem))
// if "index of the set" has some special meaning in your question,
// you should save it along with the set
return first.index();
for (int i = 1; i < sets.size(); i++) {
Set cur = sets.get(i);
if (cur.contains(elem)) {
sets.set(i, sets.get(i - 1));
sets.set(i - 1, cur);
return cur.index();
}
}
return -1; // not found
}https://stackoverflow.com/questions/24094784
复制相似问题