Какую структуру данных выбрать для подсчета элементов?
Здравствуйте! Дано - массив структур, отвечающий за информацию о транспортных остановках - вид транспорта, маршрут транспорта, etc. Нужно для конкретного транспорта вывести номер маршрута с наибольшими остановками. Я понимаю примерно как это сделать (брать каждый маршрут и проходиться по массиву в поисках соответствий и увеличивая счетчик совпадений для каждого маршрута), но не могу понять, какую СД для этого использовать - есть мысли насчет бинарного дерева поиска, либо хеш таблицы (склоняюсь к первому). Можете подсказать, какая структура для данной задачи будет наиболее оптимальной? Спасибо
Вам нужен std::map или std::unordered_map. Самому писать структуру данных не надо.
Первое будет деревом поиска, второе - хештаблицей.
Дерево поиска гарантированно будет работать стабильно быстро. Хеш таблица будет работать быстрее, но если вам не повезет, то может работать очень долго. Но предпочтительнее, на мой взгляд, таблица.
В качестве ключа используйте пару {Тип транспорта, номер маршрута}. В качестве значения - счетчик остановок.
Еще вам нужен еще один map из тип транспорта-> std::set или std::unordered_set номеров маршрутов.
Для построения структур один раз приходитесь по всем остановкам и увеличивайте счетчик в первой структуре. Добавляйте маршрут к транспорту во второй структуре.
Для поиска ответа пройдитесь циклом по всем элементам set из второго map - это все маршруты. Смотрите в первом map'е сколько остановок у этого маршрута и выбирайте максимум.
Простой
