java - 降低时间复杂度

Question

我有一个包含 statusEnum 的对象列表。现在，我想返回属于所提供状态的特定列表的所有对象。

一个简单的解决方案是在对象列表上循环，然后在提供的 statusEnums 列表上进行另一个 for 循环...但是，这会起作用，它会使时间复杂度为 O(n)^ 2.有没有办法可以将其减少到 O(n) ？

我无法更改 map 。我能想到的唯一其他解决方案是维护另一个基于 statusEnums 的映射作为键，但这会大大增加空间复杂性。

编辑

• 我有对象的 hashMap(我说的是一个列表)

这是我为其他人想出的代码......

public List<MyObjects> getObjectsBasedOnCriteria (List<ObjectStatus> statuses, String secondCriteria){
    EnumSet<ObjectStatus> enumSet = EnumSet.copyOf(statuses);
    for (Map.Entry<Long, MyObject> objEntry : myObjs.entrySet()){
        MyObjects obj = objEntry.getValue();
        if (enumSet.contains(obj.getStatus()) && obj.equals(secondCriteria)){
        ...
        }
    }
}

Answer 1

使用 Set 来保存 statusEnums(可能是 EnumSet)，并使用 set.contains(object.getStatus()) 检查每个实例的状态是否在该集合中 ，或者其他什么。

EnumSet 和 HashSet 中的查找时间复杂度为 O(1)，因此解决方案是线性的(假设每个对象只有一个状态)。 EnumSet.contains 比使用枚举值的 HashSet.contains 更高效；但是，选择与总体时间复杂度无关。