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

Автор ved_vijay_d, 4 года назад, По-английски

I used a vector of strings to solve this problem — https://codeforces.com/problemset/problem/4/C

I got a TLE on this, afterwards I saw some other people used map instead of a vector. Could someone kindly inspect my code and explain where I went wrong and tell me why using map is better. My code — https://codeforces.com/contest/4/submission/85707717

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

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Both find and count take O(n) for a vector, but O(log n) for a map. Generally if you need to check if something exists quickly, you should use a map or set.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

find is $$$O(N)$$$, so you code runs in $$$O(N^2)$$$. I would imagine that find just does a for loop until it finds the element. map::count and map::find both work in $$$O(\text{log}(N))$$$ because of the way map works (the keys are ordered). I think the use case for vector over map is when you only need to store things with indices small enough so that the vector doesn't consume too much memory, e.g. frequencies of characters in a string or values of some function.