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

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;
   }
}

如果两个部门的员工人数相同，则返回哪个部门并不重要。

谢谢！

Answer 1

创建部门 ID 的地图 ->很重要。

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

该算法类似于：

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

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

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

Answer 2

这是一个普通的 Java 8 解决方案：

Employee.getAllEmployees()
        .stream()
        .collect(Collectors.groupingBy(Employee::getDepartment, Collectors.counting()))
        .entrySet()
        .stream()
        .max(Comparator.comparing(Entry::getValue))
        .ifPresent(System.out::println);

它最多遍历员工列表两次。如果您愿意添加第三方依赖项，则使用 jOOλ 的等效解决方案如下

Seq.seq(Employee.getAllEmployees())
   .grouped(Employee::getDepartment, Agg.count())
   .maxBy(Tuple2::v2)
   .ifPresent(System.out::println);

：(免责声明：我在 jOOλ 背后的公司工作）

Answer 3

我会使用 Guava 执行类似的操作：

Multiset<Department> departments = HashMultiset.create();
for (Employee employee : employees) {
  departments.add(employee.getDepartment());
}

Multiset.Entry<Department> max = null;
for (Multiset.Entry<Department> department : departments.entrySet()) {
  if (max == null || department.getCount() > max.getCount()) {
    max = department;
  }
}

您需要正确实现 equals 和 hashCode 在 Department 上才能正常工作。

这里还有一个问题提到了创建未来的“排行榜”类型 Multiset 将根据其包含的每个条目的数量来维护订单。

Answer 4

由于您只想统计员工数量，因此制作地图相对容易。

HashMap<Department, Integer> departmentCounter;

将部门映射到员工数量（您增加每个员工的计数）。或者，您可以使用列表将整个 Employee 存储在地图中：

HashMap<Department, List<Employee>> departmentCounter;

并查看列表的大小。

如果你不知道如何使用该类，可以查看HashMap文档：
http://download.oracle.com/javase /1.4.2/docs/api/java/util/HashMap.html

提示：您需要使用 HashMap.keySet() 来查看已输入哪些部门。

Answer 5

我会这样做，modulo == null 和 isEmpty 检查：

public static <C> Multimap<Integer, C> getFrequencyMultimap(final Collection<C> collection,
    final Ordering<Integer> ordering) {
    @SuppressWarnings("unchecked")
    Multimap<Integer, C> result = TreeMultimap.create(ordering, (Comparator<C>) Ordering.natural());
    for (C element : collection) {
        result.put(Collections.frequency(collection, element), element);
    }
    return result;
}

public static <C> Collection<C> getMostFrequentElements(final Collection<C> collection)       {
    Ordering<Integer> reverseIntegerOrdering = Ordering.natural().reverse();
    Multimap<Integer, C> frequencyMap = getFrequencyMultimap(collection, reverseIntegerOrdering);
    return frequencyMap.get(Iterables.getFirst(frequencyMap.keySet(), null));
}

还有 CollectionUtils.getCardinalityMap() 它将完成第一种方法的工作，但这更灵活更偏向番石榴。

请记住，C 类应该得到很好的实现，即具有 equals()、hashCode() 并实现 Comparable。

这是您可以使用它的方式：

Collection<Dummy> result = LambdaUtils.getMostFrequentElements(list);

作为奖励，您还可以使用类似的方法获取频率较低的元素，只需使用 Ordering.natural() 提供第一个方法并且不要反转它。