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

Why O(n) solution gives me TLE?
Автор Loser_, история, 5 лет назад, По-английски

In this problem , I take the input and I store every value in ith index to a map.If my map[i] has a value than I push both map[i] and i to a vector pair. Here in worst case the code may run in 2*n times which is so to say O(n)times.But how I am getting here TLE with O(n) times? My submission is here.

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

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

std::map works for O(logn). and your time complexity is O((2 * N) * (2 * log(5000))). try to sort your array and find answer for O(N). total time complexity will be O((2 * N) * log(2 * N) + (2 * N)). it is will be work, imho

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

I made your solution pass by modifying a few things Submission

When using maps try to avoid using the []operator instead use count to avoid inserting extra values Reference
And I also used erase instead of setting the value to 0

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

Try using an array sized 5000, instead of std::map (that will be) sized 5000.

→ Ответить