如何高效查询指定人员列表对应的分组？求优化方案

场景说明 #

某班级包含P1-P6等人员，存在G1-G6等好友分组，例如G1包含P1、P2、P3、P4，G2包含P1、P3、P4。

已知信息 #

• 班级人员列表；
• 工具函数getGroups(Person)：返回某人员所属的分组列表，例如调用getGroups(P1)会返回[G1,G3,G2,...]；
• 工具函数getPersons(Group)：返回某分组的人员列表，例如调用getPersons(G1)会返回[P2,P1,P3,...]；注意：无法直接遍历所有分组，也不知道分组总数。

需求 #

给定人员列表（如[P1,P3,P2,P4]），找出所有成员均属于该列表的分组。例如输出[G1,G2]，而G3因包含不在查询列表的P5会被排除。

现有解法 #

遍历每个人员及其所属分组，检查分组人员是否都在已跟踪人员中，代码如下：

personsTracked = []
result = []
for (Person person : persons) {
  personsTracked.add(person) // 用personsTracked避免重复添加分组到result
  groupsPersonBelongsTo = person.getGroups()
  for (Group group : groupsPersonBelongsTo) {
    if (personsTracked.containsAll(group.getPersons())):
      result.add(group)
  }
}

现有解法存在重复处理同一分组、存在性检查效率低、结果可能重复添加等问题，以下是更优的实现思路：

1. 用HashSet优化存在性检查效率 #

将查询人员列表转换为HashSet，把成员存在性检查的时间复杂度从O(n)（ArrayList的contains方法）降到O(1)，大幅提升检查速度。

2. 避免重复处理同一分组 #

用一个HashSet记录已经处理过的分组，因为不同人员可能属于同一个分组，跳过已处理的分组可以避免重复计算。

3. 直接用完整查询集合判断分组合法性 #

原解法中personsTracked是逐步添加的，可能导致同一个分组被多次触发检查。直接使用完整的查询人员集合判断分组所有成员是否都在其中，逻辑更直观，也不会出现漏判。

4. 提前过滤成员数超标的分组 #

如果分组的成员数量大于查询人员的数量，该分组不可能是查询列表的子集，可以直接跳过检查，节省时间。

优化后代码示例 #

// 把查询人员转成HashSet，提升存在性检查效率
Set<Person> queryPersonsSet = new HashSet<>(persons);
// 用Set存储结果，自动去重
Set<Group> resultGroups = new HashSet<>();
// 记录已处理的分组，避免重复计算
Set<Group> processedGroups = new HashSet<>();

for (Person person : persons) {
    List<Group> groups = getGroups(person);
    for (Group group : groups) {
        if (processedGroups.contains(group)) {
            continue;
        }
        processedGroups.add(group);
        
        // 提前过滤：分组成员数超过查询列表，直接跳过
        List<Person> groupMembers = getPersons(group);
        if (groupMembers.size() > queryPersonsSet.size()) {
            continue;
        }
        
        // 检查分组所有成员是否都在查询集合中
        boolean isQualified = true;
        for (Person member : groupMembers) {
            if (!queryPersonsSet.contains(member)) {
                isQualified = false;
                break;
            }
        }
        
        if (isQualified) {
            resultGroups.add(group);
        }
    }
}

// 转成需要的List格式输出
List<Group> result = new ArrayList<>(resultGroups);

内容的提问来源于stack exchange，提问作者prasuna_16