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

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

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
  • Проголосовать: не нравится

»
8 лет назад, # |
← 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);

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +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.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks @gongy here's my code with same approach giving WA. Could you please identify where I am getting wrong.

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Line 27/28 don't make sense. If the current most frequent string is equal to the one you are decrementing, it doesn't necessarily decrease the maximum frequency, because there could be another string with that frequency.

      → Ответить