Это все о структуре данных.
Вам нужно прочитать поток ввода, прочитать дату, найти старые итоги за этот месяц и добавить новое количество долларов и дней обратно в итог. (Везде, где я говорю «месяц», я имею в виду месяц + год для ясности).
Простой массив по месяцам будет работать, но поскольку количество месяцев является переменной величиной, это потребует от программы считывания входных данных дважды, чтобы увидеть диапазон массива, или сохранения их всех в памяти, что потенциально невозможно. И это плохая структура по другим причинам.
Следующим шагом является связанный список, содержащий структуру данных, которая включает месяц и итоги в качестве значений. Но для этого вам потребуется найти, есть ли месяц в списке, который равен O (n) для каждой строки ввода.
Еще один шаг вверх. Хранить месяц/сумму в двоичном дереве, отсортированном (индексированном) по месяцам - "отсортированный список". Чтобы найти подходящий месяц, используется журнал заказов (месяцы во входном потоке), который не может быть слишком большим, так как даже 10 лет - это всего 120 месяцев. Преимущество этого заключается в том, что вам не придется снова сортировать данные для выходного отчета, и, вероятно, они хотят, чтобы вы его использовали.
Вероятно, наиболее эффективной структурой является то, что иногда называют «словарем». Излишне, если у вас нет тысяч месяцев. http://www.dotnetperls.com/dictionary объясняет эту структуру данных. В других средах есть похожие вещи; это вариант стандартной хеш-таблицы. Различные классы Dictionary имеют вспомогательные функции, которые сообщают вам количество значений, перечисляют ключи, сообщают вам, существует ли уже ключ и т. д. - то, что вам нужно. Вы должны использовать месяц/год в качестве ключа и количество долларов и количество клиентов в качестве сохраненных значений. Словари имеют постоянное время, поэтому они эффективны (но я подозреваю, что это излишне).
person
Peter Webb
schedule
02.06.2013
