Блог пользователя jrrain

Find most frequent word in stream of k words
Автор jrrain, история, 10 лет назад, По-английски

I was solving this. My approach uses a queue to store k elements.A map and set are are also used in order to get most frequent lexicographically smallest string. But if I am using set to find lexicographically smallest frequent string it is getting tle. Please suggest some optimisations!.Here's my code

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

In most cases such complexity is efficient. Try to switch to unordered map,set. Also for faster io speed use ios_base::sync_with_stdio(false);

→ Ответить
»
10 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

You can improve the complexity by storing a set of strings for each frequency. When you modify the count of a certain word you can move it into the appropriate set. Then you can just read the string at the start of the set of the maximum count which you are maintaining.

Also to improve your speed 1. use stdio (scanf/printf) when there are long strings or even getchar 2. once you read in a string cache it using map to an integer so you can avoid passing around heavy strings and just use integers.

→ Ответить