假设我有一个 Employee
对象的 List
。 Employee
对象有一个 getDepartment
方法,该方法返回一个 Department
对象。我想遍历该列表以找到拥有最多 Employee 的部门(即最常从 getDepartment 返回的 Department 对象)。最快的方法是什么?
public class Employee{
static allEmployees = new ArrayList<Employee>();
int id;
Department department;
public Employee(int id, Department department){
this.id = id;
this.department = department;
allEmployees.add(this);
}
public Department getDepartment(){
return department;
}
public static List<Employee> getAllEmployees(){
return allEmployees;
}
}
public class Department{
int id;
String name;
public Department(int id){
this.id = id;
}
public String getName(){
return name;
}
}
如果两个部门的员 worker 数相同,则返回哪个部门并不重要。
谢谢!
最佳答案
创建部门 ID -> 计数的 map 。
这样你就可以通过 id 获得所有计数的集合。您还可以维护一个最大项,它是对具有最高计数的 map 条目的引用。
算法类似于:
1) 初始化Map和currentMax
2)循环遍历员工
3)对于每个员工,获取其部门ID
4)执行类似map.get(currentId)的操作
a) 如果当前计数为空,则初始化它
5) 增加计数
6) 如果增加的计数 > currentMax,则更新 currentMax
该算法的运行时间为 O(n);我认为你没有比这更好的了。它的空间复杂度也是 O(n),因为计数的数量与输入的大小成正比。
如果您愿意,您可以创建一个使用组合(即包含一个映射和一个列表)的类,并且还管理保留指向具有最高计数的条目的指针。这样你的这部分功能就被正确封装了。这种方法的更大好处是,它允许您在将项目输入到列表中时维护计数(您可以代理将员工添加到列表中的方法,以便他们更新 map 计数器)。但可能有点过分了。
关于java - 从列表中查找最常见的对象,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5084796/