FloydReme
@FloydReme
Пишу музыку и программирую

Какую структуру данных выбрать для подсчета элементов?

Здравствуйте! Дано - массив структур, отвечающий за информацию о транспортных остановках - вид транспорта, маршрут транспорта, etc. Нужно для конкретного транспорта вывести номер маршрута с наибольшими остановками. Я понимаю примерно как это сделать (брать каждый маршрут и проходиться по массиву в поисках соответствий и увеличивая счетчик совпадений для каждого маршрута), но не могу понять, какую СД для этого использовать - есть мысли насчет бинарного дерева поиска, либо хеш таблицы (склоняюсь к первому). Можете подсказать, какая структура для данной задачи будет наиболее оптимальной? Спасибо
  • Вопрос задан
  • 101 просмотр
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Вам нужен std::map или std::unordered_map. Самому писать структуру данных не надо.

Первое будет деревом поиска, второе - хештаблицей.
Дерево поиска гарантированно будет работать стабильно быстро. Хеш таблица будет работать быстрее, но если вам не повезет, то может работать очень долго. Но предпочтительнее, на мой взгляд, таблица.

В качестве ключа используйте пару {Тип транспорта, номер маршрута}. В качестве значения - счетчик остановок.

Еще вам нужен еще один map из тип транспорта-> std::set или std::unordered_set номеров маршрутов.

Для построения структур один раз приходитесь по всем остановкам и увеличивайте счетчик в первой структуре. Добавляйте маршрут к транспорту во второй структуре.

Для поиска ответа пройдитесь циклом по всем элементам set из второго map - это все маршруты. Смотрите в первом map'е сколько остановок у этого маршрута и выбирайте максимум.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы