8

Есть список, состоящий из объектов. Все эти объекты отличаются значением одного поля. Задача состоит в том, чтобы вывести количество объектов для каждого значения этого поля.

1
  • Постарайтесь писать более развернутые вопросы. Поясните, в чем именно вы видите проблему. Приведите пример кода.
    – Kromster
    15 фев 2016 в 6:58

2 ответа 2

11

Пусть список называется list, а поле по которому считаем называется Name, тогда

var result = list.GroupBy(n => n.Name).Select(m => new {m.Key, Count = m.Count()});

Это у нас будет LINQ вариант, на тот случай если не захотите создавать свой "велосипед", а воспользуетесь штатными средствами языка. В противном случае @rdorn дал отличный ответ.

1
  • После фигурной скобки поставьте обычную, а то народ любит тут копипастить)) 15 фев 2016 в 6:25
8

Наивный алгоритм:

  1. Создаем Dictionary со значением проверяемого поля в качестве ключа и счетчиком найденных объектов в качестве значения
  2. Для каждого объекта объекта из списка:
    • Добавляем новую запись в Dictionary, если обнаруженный ключ отсутствует.
    • Увеличиваем счетчик найденного значения на единицу если ключ уже есть в Dictionary.
  3. Выводим значения счетчиков Dictionary

UPD
Сложность алгоритма порядка O(N), где N - длина списка. Согласно исходникам Dictinary использует хеширование ключей и сложность поиска по ключу порядка O(1).

4
  • Поиск в Dictionary O(1), так что общая асимптотика должна быть O(N). Использование HashTable не должно давать выигрыша.
    – VladD
    15 фев 2016 в 7:06
  • @VladD спасибо, перепроверю и поправлю.
    – rdorn
    15 фев 2016 в 8:52
  • @VladD исправил, приятно что теперь можно полагаться не только на слова. Меня помниться очень упорно убеждали в обратном где-то год назад, и надо сказать успешно, поэтому и засомневался.
    – rdorn
    15 фев 2016 в 9:16
  • Возможно, те. кто убеждал вас, перепутали с std::map из C++, там не хеш-таблица, а дерево.
    – VladD
    15 фев 2016 в 9:18

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.