如何在java中使用Map来降低两个嵌套循环的时间复杂度

Question

我有两个employeeData对象列表

List<EmployeeDatas> allEmployees
List<EmployeeDatas> currentEmployees
Class EmployeeDatas {
String name;
String lastName;
String joiningDate;
String promotionDate;
}

我想比较第二个列表数据与第一个列表数据，而不使用双嵌套循环

如果数据匹配返回true，否则返回false。

for (allEmployee : allEmployees) {
for ( currentEmployee : currentEmployees ) {
if(allEmployee.name.equal(currentEmployee.name) &&   
allEmployee.lastName.equal(currentEmployee.lastName) && 
allEmployee.joiningDate.equal(currentEmployee.joiningDate) &&
allEmployee.promotionDate.equal(currentEmployee.promotionDate)) {
return true;
}
}
}

是否有可能使用Map并在O(N)而不是O(N^2)时间内解决它

Answer 1

您可以使用HashSet来实现此目的。但要做到这一点，您需要正确实现equals/hashCode合约。

下面是一个例子:

public class EmployeeData {
private String name;
private String lastName;
private String joiningDate;
private String promotionDate;

@Override
public boolean equals(Object o) {

return o instanceof EmployeeData other
&& Objects.equals(name, other.name)
&& Objects.equals(lastName, other.lastName)
&& Objects.equals(joiningDate, other.joiningDate)
&& Objects.equals(promotionDate, other.promotionDate);
}

@Override
public int hashCode() {
return Objects.hash(name, lastName, joiningDate, promotionDate);
}
}

现在要检查currentEmployee列表中是否至少有一个雇员存在于allEmployees中，您可以将allEmployees的内容转储到HashSet中，并遍历currentEmployee，根据该集合检查元素。这种检查的平摊代价为O(1)，因此总体时间复杂度为O(n)(*n -表示currentEmployee列表中元素的个数)

public static boolean containsAny(List<EmployeeData> allEmployees,
List<EmployeeData> currentEmployees) {

Set<EmployeeData> allEmp = new HashSet<>(allEmployees);
for (EmployeeData currentEmployee : currentEmployees) {
if (allEmp.contains(currentEmployee)) {
return true;
}
}
return false;
}

我们可以通过使用流API来使这段代码非常简洁。

public static boolean containsAny(List<EmployeeData> allEmployees,
List<EmployeeData> currentEmployees) {

Set<EmployeeData> allEmp = new HashSet<>(allEmployees);

return currentEmployees.stream().anyMatch(allEmp::contains);
}

注意:此代码的行为与提供给您的代码片段完全相同，即它将在第一次匹配后返回。

如果你想知道是否所有元素currentEmployee列表中的currentEmployee都存在，那么您可以使用Collection.containsAll():

方法

public static boolean containsAll(List<EmployeeData> allEmployees,
List<EmployeeData> currentEmployees) {

Set<EmployeeData> allEmp = new HashSet<>(allEmployees);

return allEmp.containsAll(currentEmployees);
}