java - 从列表中查找最常见的对象

Question

假设我有一个 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 数相同，则返回哪个部门并不重要。

谢谢!

Answer 1

创建部门 ID -> 计数的 map 。

这样你就可以通过 id 获得所有计数的集合。您还可以维护一个最大项，它是对具有最高计数的 map 条目的引用。

算法类似于:

1) 初始化Map和currentMax
2)循环遍历员工
3)对于每个员工，获取其部门ID
4)执行类似map.get(currentId)的操作
a) 如果当前计数为空，则初始化它
5) 增加计数
6) 如果增加的计数 > currentMax，则更新 currentMax

该算法的运行时间为 O(n)；我认为你没有比这更好的了。它的空间复杂度也是 O(n)，因为计数的数量与输入的大小成正比。

如果您愿意，您可以创建一个使用组合(即包含一个映射和一个列表)的类，并且还管理保留指向具有最高计数的条目的指针。这样你的这部分功能就被正确封装了。这种方法的更大好处是，它允许您在将项目输入到列表中时维护计数(您可以代理将员工添加到列表中的方法，以便他们更新 map 计数器)。但可能有点过分了。