java - 在 Java 中比较具有最小时间复杂度的列表

Question

我有两个列表

List<MyData> listA = new ArrayList<MyData>()和 List<MyData> listB = new ArrayList<MyData>()都包含 MyData 类型的对象和 MyData包含这些变量。

Class MyData {
    String name;
    boolean val
}

我必须编写一个程序来比较两个 arraylist 是否相等，时间复杂度较低。我不会覆盖 Mydata 类中的 equals 和 hashcode，因为它是一个已经存在的类，修改可能会影响应用程序的不同行为。 我写的代码是

forEach(MyData a:listA ){

    forEach(MyData b:listB ){
        if(a.getName.equals(b.getName)){
        }

    }
}

Answer 1

首先 forEach 不是有效的 Java 语法。它应该是for。

其次，您不希望有一个嵌套循环，因为这会给您O(n^2) 时间复杂度。

你应该有一个循环遍历两个列表:

if (listA.size() != listB.size())
    return false;
for (int i = 0; i < listA.size(); i++){
    MyData a = listA.get(i);
    MyData b = listB.get(i);
    if (!a.getName.equals(b.getName))
        return false;
}
return true;

这会给你 O(n) 时间复杂度。