首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >C++/JAVA:高效地在集合中找到包含给定值的集合

C++/JAVA:高效地在集合中找到包含给定值的集合
EN

Stack Overflow用户
提问于 2014-06-07 07:15:00
回答 2查看 123关注 0票数 6

假设我们有一个相互排斥的集合。

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)更快的方式(或任何数据结构来存储这些集)吗?

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2014-06-07 07:47:04

您可以创建一个映射来映射一个值来设置id(例如,它应该将1、2、3映射到A、4、5和6映射到B等等)。有了散列映射,它平均可以在O(1)中工作。

票数 4
EN

Stack Overflow用户

发布于 2014-06-07 12:47:56

作为一个快速的启发,可以帮助尝试泡泡,最积极地使用在列表中的设置。很可能大多数情况下会有一到两组在80%-90%的请求中返回。

代码语言:javascript
复制
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
}
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/24094784

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档