Есть простейшая задача, описанная ниже. Каким бы способом вы бы решили её? Прошу ответить по формату, описанном мною ниже. Моя мысль заключается в создании двухмерного массива, но, очевидно, что я мыслю в данный момент неправильно.
На вход подается N - количество строк, которые будут введены в программу. Сразу после ввода N вводятся определенные значения K - индификатор студента (ID).Значение К может быть очень велико. Если встречается K c определенным значением, например, 1043, то мы должны увеличить личную переменную студента Count на единицу.
Задача: вывести максимальный Count и соответствующий ему ID.
Пример ввода:
5
1029
1011
1029
8
78
Вывод:
2 1029
Иными словами, нужно определить, какое число встречается чаще всех и вывести значение, сколько раз встретилось это число.
Вопросы 1) Каким образом лучше реализовать эту задачу? Можно ли обойтись без создания огромного двухмерного массива? 2) Какие вообще есть варианты решения задачи кроме самого оптимального, описанного Вами в пункте 1)
UPD: Очевидно, что решить задачу можно с использованием динамических структур данных вроде хэш-таблиц или деревьев, как подметили в ответе на вопрос. Однако меня интересует решение с использованием стандартных средств языка без создания структур данных. Если такое решение невозможно, буду рад увидеть ваши предложения по решению
Я предлагаю такой алгоритм:
1. Взять динамическую структуру данных, позволяющую быстро добавлять и искать элементы (дерево, хеш-таблица).
2. К каждому элементу добавить счетчик повторений.
3. Поддерживать две глобальных переменных: ID_MAX и Count_MAX.
4. Сравнивать Count_MAX с очередным обновленным счетчиком и переприсваивать ID_MAX и Count_MAX, если обновленный счетчик превысит Count_MAX.
5, Вывести ID_MAX и Count_MAX.
P.S. А зачем здесь двумерный массив?
Простой
Средний