Этот вопрос был размещен на Leetcode здесь .
Разработать структуру данных, которая может возвращать ключевое слово с наибольшим трендом. Временная сложность должна быть минимально возможной. TBH Я пока не знаю, каким может быть оптимальное решение.
Учитывая 2 параметра в качестве ввода:
Параметр 1: Строка Имя пользователя
Параметр 2: массив строк, содержащий ключевые слова, написанные пользователем в Твиттере.
Объявление функции: твит функции (имя пользователя, ключевые слова []) {};
Пример 1:
tweet("User1",["love","dog"])
tweet("User2",["cat"])
tweet("User3",["walk","cat"])
tweet("User2",["dog"])
tweet("User3",["like","dog"])
ключевое слово с популярностью: собака
Пример 2:
a. tweet("User1",["Dog"])
b. tweet("User1",["like","Dog"])
c. tweet("User1",["love","Dog"])
d. tweet("User1",["walk","Dog"])
e. tweet("User1",["hate","Dog"])
f. tweet("User2",["like","cat"])
g. tweet("User3",["cat"])
ключевое слово: кошка
Объяснение: учитывайте только количество уникальных пользователей, которые твитнули определенное ключевое слово при расчете ключевого слова с наибольшей популярностью.
По этому вопросу я смог найти решение с использованием (аналогично тому, что размещено в Leetcode здесь )
1. Карта, которая содержит набор слов для данного пользователя,
2. Карта, которая содержит слово и его уникальное количество пользователей.
3. Max Heap -> используется для получения верхнего слова на основе частоты.
Тем не менее, для всех слов, которые уже есть в карте 2, если я добавлю его в PQ, мне нужно будет выполнить операцию удаления O (n), а затем снова добавить ее с повышенной частотой в PQ.
например. в примере 2 выше, до операции е
After a, Map1-[<User1,[Dog]>], Map2- [[<Dog,1>], PQ-[1-Dog]
After b, Map1-[[<User1,[Dog,like]>]], Map2- [<Dog,1>,<like,1>], PQ-[1-Dog,1-like]
...
После е
Map1- [[<User1,[Dog,like,love,walk,hate]>]],
Map2- [<Dog,1>,<like,1>,<love,1>,<walk,1>,<hate,1>],
**PQ-[1-Dog,1-like,1-love,1-walk,1-hate]**
После f,
Map1- [<User1,[Dog,like,love,walk,hate]>,<User2,[like,cat]>],
Map2- [<Dog,1>,<like,2>,<love,1>,<walk,1>,<hate,1>,<cat,1>],
**PQ- [2-like,1-Dog,1-love,1-walk,1-hate]**
У меня такой вопрос: после добавления записи «User2 - like, cat» на шаге f выше, мне нужно повторно сбалансировать максимальную кучу, то есть удалить «like» и добавить его обратно. Так что теперь это наверху кучи.
Это оптимальный путь? Или я могу оптимизировать это дальше. Чтобы я не брал на себя расходы на удаление () или изменение баланса.
Я тоже пытался использовать TreeMap, но не могу понять структуры данных.