Найти наиболее распространенный объект из списка

Question

Допустим, у меня есть List из Employee объектов. Объекты Employee имеют метод getDepartment, который возвращает объект Department. Я хочу перебрать этот список, чтобы найти отдел с наибольшим количеством Employee с (т.е. объект Department чаще всего возвращается из getDepartment). Какой самый быстрый способ сделать это?

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

создать карту идентификатора отдела -> счета.

таким образом вы получите коллекцию всех подсчетов по идентификатору.Вы также можете сохранить максимальный элемент, который является ссылкой на запись карты с наибольшим количеством.

алгоритм будет выглядеть примерно так:

1) Инициализировать карту и currentMax
2) перебрать сотрудников
3) для каждого сотрудника получить идентификатор отдела
4) сделать что-то вроде map.get (currentId)
a) если текущий счетчик равен нулю, инициализировать его
5) увеличить счетчик
6) если счетчик увеличен> currentMax, обновить 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

Я бы сделал что-то подобное, используя Гуава :

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

Я бы сделал это так, по модулю == 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 () и не меняйте его.

Answer 5

Поскольку вы просто хотите считать сотрудников, составить карту относительно просто.

HashMap<Department, Integer> departmentCounter;

, который отображает отделы на количество сотрудников (вы увеличиваете количество для каждого сотрудника). Кроме того, вы можете сохранить на карте всего Сотрудника со списком:

HashMap<Department, List<Employee>> departmentCounter;

и посмотрите на размер ваших списков.

Тогда вы можете посмотреть документацию по HashMap, если не знаете, как использовать класс: http://download.oracle.com/javase/1.4.2/docs/api/java/util/HashMap.html

Подсказка: вам нужно использовать HashMap.keySet (), чтобы увидеть, какие отделы были введены.