Итак, вы подумали об использовании хэш-карты лет для хеш-карт жанров для хеш-карт имен частот.Имеет ли это смысл?Конечно.Это хороший способ решить вашу проблему?Скорее всего нет.Также, как вы говорите, можно также использовать одну основную хэш-карту лет для коллекций кортежей с частотами жанровых имен (или структур во многих языках, таких как C, C ++, Java и т. Д.).Что касается коллекций, вы думали о связанных списках, но вы вполне могли бы использовать векторы или что-то еще (связанные списки очень часто являются худшим видом структур данных).Но это не будет более эффективным и не обязательно будет лучшим способом решения вашей проблемы, даже если он может быть более читабельным и обслуживаемым.
Я не буду говорить об улучшениях производительности, которые не влияют на времясложность, так как вы ясно дали понять в комментариях, что это для экзамена, который заботится только о сложности времени (что печально, но не важно).Кроме того, я предполагаю, что это единственная проблема, которую вам нужно решить.
Давайте посмотрим, как улучшить ваши идеи.Так уж сложилось, что сочетание обоих ваших решений вместе с одним улучшением дает наилучшее возможное решение с точки зрения сложности времени, то есть O(k).Во-первых, обратите внимание, что каждое название фильма связано только с одной частотой, а каждая частота связана (вероятно) только с одним именем фильма.А поскольку вы хотите получать названия фильмов на основе частот, у хэш-карты нет преимущества перед линейным набором пар имя-частота, таких как вектор или связанный список.Затем обратите внимание, что каждый год и каждый жанр (независимо) связаны с несколькими фильмами (каждый из которых имеет название и частоту).Таким образом, здесь есть место для хэш-карты: для данного года и данного жанра структура, подобная хэш-карте, даст вам подходящие фильмы в ожидаемое постоянное время.
Объедините эти два результата, и вы получите хэш-карту с годами.и жанры в качестве ключей и коллекции пар имя-частота в качестве значений.Единственное улучшение, которое позволяет извлекать k большинство потоковых фильмов за данный год и жанр в O(k) сложности времени, является своего рода: если ваши пары имя-частота сортируются по частоте в каждой коллекции, вы можете просто вернутьfirst (или last, в зависимости от порядка) k names.
Одна деталь, которая может показаться вам странной, состоит в том, что в хэш-карте используются как годы, так и жанры в качестве ключей.Это деталь реализации.Вы можете сделать это с помощью двух вложенных хэш-карт, один из которых использует года в качестве ключей, а другой - жанры, или вы можете комбинировать годы и жанры и напрямую использовать эти пары в качестве ключей.На самом деле это просто для пар хеш-год-жанр.